5
$\begingroup$

I learned the following proposition (in which there is no proof) in a GRE math preparation book. I don't understand what it means and I am not able to find any theorem about this statement in Hardy's An Introduction to the Theory of Numbers.

For any positive integer $c$, the statement $a\equiv b \pmod n$ is equivalent to the congruences $a\equiv b,b+n,b+2n,\dots,b+(c-1)n\pmod {cn}.$

I cannot even apply this proposition to an example such as $7\equiv 1\pmod 6$. If the above is true, then

$7\equiv 1,7,13,19\pmod{24}$ which is obvious not true.

Is there any typo here? Or how should I understand this "proposition"?

Edit: This question may be related to the question here.

Added:

How should I prove this proposition?

  • 0
    @Jack:I see there is$a$reference-request tag, so I mention here the book ***Disquisitiones Arithmeticae*** by *Gauss*. Hope you enjoy it.2011-06-18

1 Answers 1

4

Just in case you are not familiar with the equivalence to congruence I am about to use:

Lemma. Let $a$, $b$, and $n$ be integers. Then $a\equiv b\pmod{n}$ if and only if there exists an integer $k$ such that $a=b+kn$.

Proof. $a\equiv b\pmod{n}$ if and only if $n|a-b$, if and only if there exists an integer $k$ such that $nk=a-b$, if and only if there exists an integer $k$ such that $b+nk = a$. QED

To prove the proposition, first assume that $a\equiv b\pmod{n}$. That means that $a=b+kn$ for some integer $k$. Therefore, $a\equiv b+kn \pmod{nc}$ holds. This looks almost like the answer we want. So the question is: what are the possible values for $kn$ modulo $nc$?

To find that out, divide $k$ by $c$ with remainder; that is, write $k=qc+r$, with $0\leq r\lt c$ (division algorithm). Then $b+kn = b+(qc+r)n = b+q(cn) + rn \equiv b+rn\pmod{cn}.$ Therefore, $a\equiv b+rn\pmod{nc},$ and $r$ is either $0$, $1$, $2,\ldots,c-1$, because it is the remainder of dividing $k$ by $c$.

Conversely, suppose that $a\equiv b+rn\mod{cn}$ for some $r$, $r=0$, $1$, $2,\ldots,c-1$. That means that $a=b+rn+k(cn)$ for some integer $k$. Then $a = b+rn+kcn = b+(r+kc)n,$ so $a =b+(r+kc)n \equiv b\pmod{n}.$

Thus, $a\equiv b\pmod{n}$ if and only if $a$ is congruent to one of $b$, $b+n$, $b+2n,\ldots,b+(c-1)n$ modulo $cn$.

  • 0
    OK. Fair enough, since you are talking about the language that *describe*$a$mathematical statement instead of the logic itself. By the way, this "every" and "each" issue is motivated by Gowers's new blog post about the [quantifiers](http://gowers.wordpress.com/2011/09/30/basic-logic-quantifiers/) I read this morning. In that article, he reads "$\forall$" as "for every" *or* "for each". Anyway, I see what you mean now. `:-)`2011-09-30