Chinese Remainder Theorem

Theorem

Let $n_1, n_2, \ldots, n_r$ be positive integer such that $n_i \perp n_j$ for all $i \ne j$ (that is, $\gcd \left\{{n_i, n_j}\right\} = 1$).

Then the system of linear congruences:

• $x \equiv b_1 \pmod {n_1}$
• $x \equiv b_2 \pmod {n_2}$
• $\ldots$
• $x \equiv b_r \pmod {n_r}$

has a simultaneous solution which is unique modulo $\displaystyle \prod_{i=1}^r n_i$.

Proof

Let $\displaystyle N = \prod_{i=1}^r n_i$ and $N_k = \dfrac N {n_k}$ for $k = 1, 2, \ldots, r$.

Because $n_i \perp n_k$ for each $i \ne k$, we have:

$\gcd \left\{{N_k, n_k}\right\} = \gcd \left\{{n_1 n_2 \cdots n_{k-1} n_{k+1} \cdots n_r, n_k}\right\} = 1$.

So by Solution of Linear Congruence, the linear congruence $N_k x \equiv 1 \pmod {n_k}$ has a unique solution modulo $n_k$.

Let this solution be $x_k$.

So $N_k x_k \equiv 1 \pmod {n_k}$

We are going to show that $x_0 = b_1 N_1 x_1 + b_2 N_2 x_2 + \cdots + b_r N_r x_r$ satisfies each of the congruences.

So, we evaluate $x_0$ modulo $n_k$ for each $k = 1, 2, 3, \ldots, r$.

We start by noting that $i \ne k \implies n_k \backslash N_i$ so $N_i \equiv 0 \pmod {n_k}$.

So for each $k = 1, 2, \ldots, r$ we have $x_0 \equiv b_k N_k x_k$ because each of the remaining terms in the sum is congruent modulo $n_k$ to $0$.

Finally, since $x_k$ was found such that $N_k x_k \equiv 1 \pmod {n_k}$ we have $x_0 \equiv b_k \pmod {n_k}$ as we claimed.

All we need to do now is show that this solution we have discovered is unique modulo $N$.

So, suppose that $x'$ is a second solution of the system.

That is:

$x_0 \equiv x' \equiv b_k \pmod {n_k}$ for each $k = 1, 2, \ldots, r$.

So each $n_k$ divides $x' - x_0$.

But because each of the moduli are pairwise coprime, we have:

$\displaystyle \prod_{i=1}^r n_i \backslash x' - x_0$

That is:

$\displaystyle x' \equiv x_0 \pmod {\prod_{i=1}^r n_i}$

as we wanted to show.

$\blacksquare$

Historical Note

This theorem was found in the Sun Tzu Suan Ching of Sun Tzu, who was active sometime between 200 and 500 C.E (nobody knows exactly when).