# Chinese Remainder Theorem (CRT)

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.

-
Why did you ask this again instead of editing your earlier question with mostly the same content? Are you trying to make things difficult for the people trying to help you? –  Jyrki Lahtonen Aug 16 '11 at 9:41
No. One of the mathematician of this site suggested me to post the same question once again as a new post!!! –  Gandhi Aug 16 '11 at 9:45
I knew there was something bugging me about the title... –  Guess who it is. Aug 16 '11 at 11:58
@Jyrki, my fault. If you look at that earlier question you'll see that I posted an answer, Gandhi then added on another question, and I suggested that the new question should be posted as a new question. I guess I should have also suggested that Gandhi include a link to the old question in the new one. –  Gerry Myerson Aug 16 '11 at 12:57
Instead of discussing too many times, is there any mathematician who can answer the above post? –  Gandhi Aug 16 '11 at 15:41

I assume that by $x_j$ you mean the solutions of congruence $x\equiv a_j\pmod{b_j}$.

Do it by induction on $n$. Here's how to do the case $n=2$, and I leave it to you to modify this so that it becomes the induction step as well. In this case $C=b_1b_2$, $c_1=b_2$ and $c_2=b_1$. So the solutions of the first congruence $x\equiv a_1\pmod{b_1}$ form the set of residue classes modulo $C$: $$x_1\in\bigcup_{m=0}^{c_1-1}(a_1+b_1m+C\mathbf{Z})=\quad\left(\bigcup_{m=0}^{c_1-1}[a_1+mb_1]\pmod{C}\right)$$ (the notation in the large parenthesis is my guess as to how you would write it, the first notation is more standard IMHO, but you may not have seen it, if you haven't studied residue class groups/rings, yet).

Let us look at the set of representatives $S_1=\{a_1+b_1m\mid m=0,1,\ldots,b_2-1\}$. I claim that they are all pairwise non-congruent modulo $b_2$. Assume contrariwise that for some $0\le m_1<m_2<b_2$ the numbers $a_1+b_1m_1$ and $a_1+b_1m_2$ have the same residue when divided with $b_2$. Then their difference $a_1+b_1m_2-(a_1+b_1m_1)=b_1(m_2-m_1)$ must be divisible by $b_2$. But $b_1$ and $b_2$ were assumed to be coprime. Therefore this can happen only, if $m_2-m_1$ is divisible by $b_2$. But that is impossible, because $0<m_2-m_1<b_2$.

[ Similarly we see that the representatives $a_2+b_2m, m=0,1,\ldots,b_1-1$ of the residue classes modulo $C$ that form the set of solutions of the second congruence $$x_2\in\bigcup_{m=0}^{c_2-1}(a_2+b_2m+C\mathbf{Z})=\quad\left(\bigcup_{m=0}^{c_2-1}[a_2+mb_2]\pmod{C}\right)$$ are pairwise non-congruent modulo $b_1$. ]

Altogether the set $S_1$ has $b_2$ integers that we just showed to be pairwise non-congruent modulo $b_2$. Therefore they must be congruent to the numbers $0,1,\ldots,b_2-1$ in some order, because between them they must cover all the residue classes modulo $b_2$. Which of these residue classes modulo $C$ appear in the set of solutions of the second congruence? A coset mod $C$ is in the second set of solutions, iff its representative is congruent to $a_2\pmod {b_2}$. Therefore exactly one element of the set $S_1$ is congruent to $a_2\pmod {b_2}$. So $a_1+b_1m\equiv a_2\pmod{b_2}$ for a unique choice of $m=m_0$ in the range $0\le m_0<b_2$. We have just shown that the intersection of the sets of solutions to the two congruences is formed by a single coset $a_1+b_1m_0+C\mathbf{Z}.$

That does it for $n=2$. Now we can add a third congruence to the mix. The third modulus $b_3$ is coprime to both $b_1$ and $b_2$, so it is coprime with the product $b_1b_2$. We can reduce the above argument with the substitutions: $a_1 \leftarrow a_1+b_1m_0$, $a_2\leftarrow a_3$, $b_1\leftarrow b_1b_2$, $b_2\leftarrow b_3$.

Edit (a bit more done at OP's request)

Above we saw that the pair of congruences $x\equiv a_i \pmod {b_i}, i=1,2$ is equivalent to the single congruence $x\equiv a' \pmod {b_1b_2}$ for a unique $a'$ in the interval $0\le a'<b_1b_2$. (using the above notation $a'=a_1+b_1m_0$.

Therefore the system of three congruences $x\equiv a_i \pmod {b_i}, i=1,2,3$ is equivalent to the pair of congruences $x\equiv a' \pmod {b_1b_2}, x\equiv a_3 \pmod {b_3}$. Here $b_1b_2$ and $b_3$ are coprime, so again by the above result this pair of congruences is equivalent to a single congruence $x\equiv a'' \pmod {((b_1b_2)b_3)}$ for a unique integer $a''=a'+m_0'b_3$ in the range $0\le a''<b_1b_2b_3$.

So the same general argument that took care of the case $n=2$ also gives us the induction step. We handle a set of $k+1$ congruences with respect to pairwise coprime moduli by applying the induction hypotheses to turn the system of first $k$ congruences to a single congruence, pair this up with the last congruence, and reuse the $n=2$ argument to get the claim of the inductive step.

-
Thank you so much for your help. very interesting... –  Gandhi Aug 17 '11 at 5:55
Jyrki sir! I need further assistance. –  Gandhi Aug 18 '11 at 16:36
I tried to use your idea to expand for induction. But, I failed. Could you explain the last part or expand your idea to a full induction. –  Gandhi Aug 23 '11 at 17:08
@Gandhi: I tried to add a bit. Ask here, if you don't understand some steps. –  Jyrki Lahtonen Aug 23 '11 at 18:44
Sir, I am extremely thankful to you. I got, what exactly I am looking for. –  Gandhi Aug 24 '11 at 17:12