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?

  • 2
    Why is it obviously not true? (The commas here mean "or.")2011-06-14
  • 1
    @Qiaochu: Aha, it's my ignorance. I thought it means "and".2011-06-14
  • 2
    @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.2011-06-14
  • 5
    Perhaps it should say "is equivalent to *one of* the congruences" (and in fact, to *exactly* one of them).2011-06-14
  • 0
    @Andres: Fair enough, it makes sense now.2011-06-14
  • 0
    @Jack: I would have been (am!) troubled by that statement, as well (as it is stated).2011-06-14
  • 0
    Hmm, such problems may usually lead to hours of confusion for a beginner, one has better have a good textbook by hand.2011-06-14
  • 0
    @Qiaochu: I got pretty confused reading the statement myself. In all my mathematical experience the comma has always meant "and". Is it usual for it to mean "or"?2011-06-14
  • 0
    @Jack What's the precise reference? (title, pub-date, page-no) Perhaps an old edition of Hardy's *Theory of Numbers*?2011-06-14
  • 0
    @Josh: I think so. For example, one often sees statements like $x^2 \equiv 0, 1, 4 \bmod 8$ in elementary number theory. If you like, you can think of this as a union instead of as an or: I am asserting that $\{ x^2 : x \in \mathbb{Z}/8\mathbb{Z} \} = \{ 0, 1, 4 \}$, but without using set-builder notation.2011-06-14
  • 0
    @Bill: This statement is not from Hardy's book. It's from a GRE preparation book. I said I was not able to find similar statement in Hardy's.:-)2011-06-14
  • 2
    @Jack Ah, yes. It does in fact look like something one might find in a very old number theory textbook.2011-06-14
  • 0
    @Qiaochu: Actually, now that I think about it you are right, I do often use commas as "or"s (when solving a quadratic for instance $x = 1, 2$).2011-06-14
  • 0
    I think the confusion here comes about by the way the OP's sentence is stated - it gives the impression that the congruence is equivalent to all those other congruences simultaneously.2011-06-14
  • 0
    @Jack: There is a hidden "duality" in the language. We can say "The solutions to $x^2=4$ are $x=2$ **and** $x=-2$", or one can say "The solution to $x^2=4$ is $x=2$ **or** $x=-2$". They are both correct (one lists all solutions, "this is a solution, and this is a solution, and this is a solution and..." The other states "the solution is that $x$ is either $2$ or $x$ is $-2$. (Note also that the first statement uses "are", the second uses "is"). Here, you can read it either way.2011-06-18
  • 0
    @Arturo: Good point. I think if one use the language of mathematical logic, then one has the exact meaning of "and" and "or". And then no confusion will appear.2011-06-18
  • 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
    @Arturo: What does the question "what can kn be modulo nc?" mean?2011-06-18
  • 1
    @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.2011-06-18
  • 0
    @Arturo: Now I see. "what are the possible values of $kn$ modulo $nc$ is more readable for me. Thanks!2011-06-18
  • 0
    @Jack: Edited, then.2011-06-18
  • 0
    @Arturo: As I understand, since $a=b+kn$, $a\equiv b+kn\pmod{nc}$ is true for all integer $k$, right? The reason you take $kn$ modulo $cn$ is to find the equivalent classes. Correct?2011-06-18
  • 1
    @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).2011-06-18
  • 0
    @Arturo: Hmm, now I see. I think this is the very difference between this proposition and the [question](http://math.stackexchange.com/q/46017/9464) from the Hardy's book I mentioned in the post.2011-06-18
  • 0
    @Arturo: If one regards $a$ as an variable, then for *every* $k$, one get the *particular* $a$. In other words, if one write $x\equiv b\pmod{n}$, one can get $c$ solutions(mod $cn$). Am I right?2011-06-18
  • 1
    @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.2011-06-18
  • 1
    @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$.2011-06-18
  • 0
    @Jack: Yes. Thanks.2011-07-30
  • 0
    I think "every" and "each" are not that different, at least in mathematical logic. Both of them suggest what you mean by *each*. What matters here is the *order* of the *quantifiers*. After all, $\forall k\exists a, s.t. a = b+kn$ and $\exists a\forall k, s.t. a = b+kn$ are totally different.2011-09-30
  • 0
    @Jack: But we are not writing mathematical logic above, we were writing in English trying to describe a mathematical statement. When you do that, "each" signals that different instances may require different processes. Compare "In a group, there is an inverse for every element" and "In a group, there is an inverse for each element"; the former may be misinterpreted as "there is a single element that works as an inverse for everyone", while I think that it would be difficult to misinterpret that latter that way.2011-09-30
  • 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