# systems of congruences and CRT

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

EDIT:

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.

• I tried $\TeX$-ing up your question, but I'm not sure what those U's in 2. are... Aug 12, 2011 at 5:12
• Hint: the remainder must be Chinese...
– gary
Aug 12, 2011 at 5:32
• @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?
– anon
Aug 12, 2011 at 5:39
• Thank you so much for editing in LATEX Aug 15, 2011 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.

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