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$