Chinese Remainder Theorem/General Result

From ProofWiki
Jump to navigation Jump to search


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

Then the system of linear congruences:

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

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


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

Let $N = n_1 \cdots n_r$.

For an integer $k$, let $\Z / k \Z$ denote the ring of integers modulo $k$.

Then we have a ring isomorphism:

$\Z / N \Z \simeq \Z / n_1 \Z \times \cdots \times \Z / n_r \Z$


Let $\displaystyle N = \prod_{i \mathop = 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 \set {N_k, n_k} = \gcd \set {n_1 n_2 \cdots n_{k - 1} n_{k + 1} \cdots n_r, n_k} = 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 \divides N_i$


$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 \mathop = 1}^r n_i \divides x' - x_0$

That is:

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

as we wanted to show.


Also see

Historical Note

The Chinese Remainder Theorem was found in the Sun Tzu Suan Ching of Sun Tzu, who was active in China sometime between $200$ and $500$ C.E (nobody knows exactly when).

The principle is believed to have been used by Chinese calendar makers as far back as $100$ C.E.