I want to establish an efficient method to solve linear congruences to prove the Chinese Remainder Theorem. I need a proper generalization/proof for the following ones to go to further developments.

  1. If $a$ and $b$ are integers, then $a \bmod b = {a, a-b, a+b, a-2b, a+ 2b,...}$

  2. Let $a_1, a_2, ... , a_n, b$ are integers, then $[a_1, a_2,...,a_n] \bmod b = (a_1 \bmod b) \cup (a_2 \bmod b ) \cup ... \cup (a_n \bmod b)$.

  3. Let $a$, $b$ and $c$ are integers with $c > 0$ then prove that $a \bmod b = [a, a+b,\dots, a+(c-1)b] \bmod cb$.


Generally, we can express 1 mod 2 in terms of modulo 8. From this we can make $1 \pmod 2 = [1, 3, 5, 7] \pmod 8$. I mean factor of 4. which is same as $[a, a+b, ..., a+ (c-1)b] \pmod{bc}$. Symbolically, $$a \pmod b = \cup_{k = 0}^{c-1} [(a -b) + kb] \pmod {bc}$$ Now the question is, in CRT (Chinese Reminder Theorem), $$x = a_1 \pmod{b_1},\, x = a_2 \pmod {b_2},\dots,\, x = a_n \pmod {b_n}$$ where $0 \le a_j \lt b_j$ and the $b_j$'s are pairwise relative primes. I think, we can rewrite the $j$th congruence by the factor $1/b_j \prod b_k = c_k$ (where the product is running from $k = 1$ to $n$). Then $b_j c_j = C = \prod b_k$ (where the product is running from $k = 1$ to $n$).

Finally we can see the $$x_j = \cup_{m = 1}^{c_j} [(a_j - b_j) + b_j m] \pmod C$$ Now I want to know the following How to prove the following by using the above information. The system of congruences (in CRT), has a solution set with $b_j$'s are relatively primes is: $$x = \cap_{j = 1}^n[\cup_{m =1}^{c_j} [(a_j -b_j) + b_j m)]\pmod C$$ where $c_j = C/b_j$ and $C = \prod_{k = 1}^n b_k$ and the intersection contains only one residue class.

  • $\begingroup$ I tried $\TeX$-ing up your question, but I'm not sure what those U's in 2. are... $\endgroup$ – J. M. is a poor mathematician Aug 12 '11 at 5:12
  • $\begingroup$ Hint: the remainder must be Chinese... $\endgroup$ – gary Aug 12 '11 at 5:32
  • 1
    $\begingroup$ @J.M.: Gandhi means to do set union on the elements of the equivalence classes, I think that's pretty clear. OP, did you know Wikipedia elaborates on a constructive algorithm for solving congruence systems? $\endgroup$ – anon Aug 12 '11 at 5:39
  • $\begingroup$ Thank you so much for editing in LATEX $\endgroup$ – Gandhi Aug 15 '11 at 8:34

Here's a start. I take it by "$a\mod b$" you mean the set of all integers $x$ such that $x\equiv a\pmod b$. By the definition of $x\equiv a\pmod b$, that's the set of all $x$ such that $x-a$ is a multiple of $b$. That is, the set of all $x$ such that $x-a$ is in $\lbrace\, 0,b,-b,2b,-2b,\dots\,\rbrace$. That is, the set of all $x$ in $\lbrace\, a,a+b,a-b,a+2b,a-2b,\dots\,\rbrace$, which is what you want (if I understand your rather non-standard notation).

EDIT: The trouble with the second question is that I don't know what you mean by $[a_1,a_2,\dots,a_n]$. For the 3rd question, I'll interpret it as asking for a proof that the class $a\pmod b$ is the union of the classes $a+tb\pmod{cb}$, $t=0,1,\dots,c-1$.

First note that if $x\equiv a+tb\pmod{cb}$ then $x-a-tb$ is a multiple of $cb$, so it's a multiple of $b$, so $x-a$ is a multiple of $b$ (since $tb$ is a multiple of $b$), so $x\equiv a\pmod b$. Thus we have proved that the union of the classes $a+tb\pmod{cb}$, $t=0,1,\dots,c-1$ is contained in the class $a\pmod b$.

Now suppose $x\equiv a\pmod b$. Then $x-a=bw$ for some integer $w$. We can divide $w$ by $c$; the division theorem says $w=cq+r$ for some integers $q$ and $r$ with $0\le r\lt c$. So $x-a=bw=b(cq+r)$, so $x-a-br=bcq$, so $x\equiv a+br\pmod{cb}$. So, everything in the class $a\pmod b$ is in one of the classes $a+tb\pmod{cb}$, and we're done.

  • $\begingroup$ You are very correct. But, I need the proof for part 2 and 3 of my questions. Then I will discuss the important facts. $\endgroup$ – Gandhi Aug 13 '11 at 4:42
  • $\begingroup$ I mean, more clearly I nedd proofs of my posted questions, which will helpful me to think/develop the facts (which I got). $\endgroup$ – Gandhi Aug 13 '11 at 5:06
  • $\begingroup$ Really good. can you see my recent post, which I add to my previous post by editing. $\endgroup$ – Gandhi Aug 13 '11 at 17:31
  • $\begingroup$ I am waiting for a proper proof from GERRY MYERSON $\endgroup$ – Gandhi Aug 14 '11 at 8:18
  • $\begingroup$ Instead of adding on to this question (when does that process stop?), why not start a new question? $\endgroup$ – Gerry Myerson Aug 14 '11 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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