Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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). – Andrés 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
up vote 4 down vote accepted

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

share|cite|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.