# Chinese Remainder Theorem

• Apr 4th 2011, 07:16 PM
steph3824
Chinese Remainder Theorem
I understand how to do the Chinese Remainder Theorem when all of the moduli are pairwise relatively prime, but I don't understand how to do it when all of the moduli are NOT pairwise relatively prime.

For example, say we have
x≡9 (mod 12)
x≡3 (mod 9)
x≡7 (mod 10)

According to my teacher this becomes
x≡1 (mod 4)
x≡3 (mod 9)
x≡2 (mod 5).
I don't understand how this was arrived at though. Could someone please clearly explain the process?
• Apr 4th 2011, 09:20 PM
veileen
x≡9 (mod 12)
x≡3 (mod 9)
x≡7 (mod 10)

x≡1 (mod 4)
x≡3 (mod 9)
x≡2 (mod 5)

Uhm, Chinese Remainder Theorem just ensure you there exist an x such that all those conditions are satisfied.

Well, you know that x≡9 (mod 12), then $x-9=M_{12} \Rightarrow x-9=M_4$ and $x-9=M_3$ (both are true).
$x-9=M_4 \Rightarrow x-1=M_4+8=M_4 \Rightarrow$ x≡1 (mod 4).

x≡3 (mod 9) Remained unchanged.

x≡7 (mod 10), then $x-7=M_{10} \Rightarrow x+3=M_{10} \Rightarrow x+3=M_2$ and $x+3=M_5$ (both are true).
$x+3=M_5 \Rightarrow x-2=M_5-5=M_5 \Rightarrow$ x≡2 (mod 5).

I considered $M_k=\left \{ mk| m\in \mathbb{Z} \right \}, k \in \mathbb{N}$. (set of multiples of a number)