The Chinese remainder theorem

In this section, we see how to solve simple simultaneous congruences modulo $n$ . This will be applied to the study of the Euler $\phi$ -function.

Theorem 1.7.33 (Chinese remainder theorem)   Let $n_1>1$ and $n_2>1$ be relatively prime integers. Then

$$x\equiv a_1 ({\rm mod} n_1), x\equiv a_2 ({\rm mod} n_2),$$ (1.6)

has a simultaneous solution $x\in \mathbb{Z}$ . Furthermore, if $x,x'$ are two solutions to (1.6) then $x'\equiv x ({\rm mod} n_1n_2)$ .

Example 1.7.34   $23\equiv 7 ({\rm mod} 8)$ and $23\equiv 3 ({\rm mod} 5)$ .

proof: $x\equiv a_1 ({\rm mod} n_1)$ if and only if $x=a_1+kn_1$ , for some $k$ . Therefore, the truth of the existence claim above is reduced to finding an integer $k$ such that $a_1+kn_1\equiv a_2 ({\rm mod} n_2)$ . Since $gcd(n_1,n_2)=1$ , there are integers $r,s$ such that $1=rn_1+sn_2$ , so $a_2-a_1-(a_2-a_1)rn_1=(a_2-a_1)sn_2$ . This implies $kn_1\equiv a_2-a_1 ({\rm mod} n_2)$ , where $k=r(a_2-a_1)$ . Thus a solution exists.

To prove uniqueness ${\rm mod} n_1n_2$ , let $x\equiv a_1 ({\rm mod} n_1), x\equiv a_2 ({\rm mod} n_2)$ and $x'\equiv a_1 ({\rm mod} n_1), x'\equiv a_2 ({\rm mod} n_2)$ . Subtracting, we get $x'\equiv x ({\rm mod} n_1)$ and $x'\equiv x ({\rm mod} n_2)$ . Since $gcd(n_1,n_2)=1$ , the result follows. $\Box$