# Why is $a\equiv b \pmod n$ equivalent to the congruences $a\equiv b,b+n,b+2n,\dots,b+(c-1)n\pmod {cn}$?

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.

How should I prove this proposition?

-
Why is it obviously not true? (The commas here mean "or.") –  Qiaochu Yuan Jun 14 '11 at 20:54
@Qiaochu: Aha, it's my ignorance. I thought it means "and". –  Jack Jun 14 '11 at 20:56
@Jack: No wonder; that's rather poorly phrased. But the idea is, for example: if $a\equiv 1\pmod{4}$, then $a$ must be congruent to either $1$ or $1+4=5$ $\bmod 8$, and must be either $1$, $5$, or $9$ $\bmod 12$, etc. –  Arturo Magidin Jun 14 '11 at 20:59
Perhaps it should say "is equivalent to one of the congruences" (and in fact, to exactly one of them). –  Andres Caicedo Jun 14 '11 at 21:02
@Jack Ah, yes. It does in fact look like something one might find in a very old number theory textbook. –  Bill Dubuque Jun 14 '11 at 23:24

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$.

-
@Arturo: What does the question "what can kn be modulo nc?" mean? –  Jack Jun 18 '11 at 5:20
@Jack: Exactly what it says; what are the possible values of $kn$ modulo $nc$? That is, what are the numbers between $0$ and $nc-1$ that can be congruent to $kn$ modulo $nc$? It is meant to explain the next sentence, but if it is confusing, I'll take it out. –  Arturo Magidin Jun 18 '11 at 5:22
@Jack: No, not for "all integers". There is a particular integer $k$ such that $a=b+kn$. And since every number is congruent to itself, $a$ is congruent to $b+kn$ for that particular integer $k$ (because $a$ and $b+kn$ are the same number). –  Arturo Magidin Jun 18 '11 at 5:30
@Jack: The connection is this: if you solve the question from Hardy's book in the case $(k,n)=1$, then you can use this result to solve the general case: write $k=dh$, $n=dm$, and $\ell=dr$. Then if $kx\equiv \ell\pmod{n}$ holds, then so does $hx\equiv r\pmod{m}$; this has a unique solution (by the relatively prime case we are assuming is done) $x\equiv t\pmod{m}$. And now, using this problem with $a=x$, $b=t$, $c=d$ gives the final answer to the other question in the general case. –  Arturo Magidin Jun 18 '11 at 5:42
@Jack: I'm not sure I understand what you write. As I've defined it, $k$ depends on all of $a$, $b$, and $n$. It's true that you can define $a$ as $b+kn$, in which case each $k$ will define an $a$ for which $a\equiv b\pmod{n}$ holds. ("Each", not "every"; slightly different here, because $a$ changes if $k$ changes; "every" suggests the same $a$ for every $k$). But, yes, there are $c$ remainders modulo $cn$ that are congruent to $b$ modulo $n$. For instance, there are $3$ remainders modulo $12=3\times 4$ that are congruent to $1$ modulo $4$, namely $1$, $5$, and $9$. –  Arturo Magidin Jun 18 '11 at 5:45