# Chinese Remainder Theorem/General Result

## Theorem

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$).

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 \mathop = 1}^r n_i$.

### Corollary

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$

## Proof

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

That is:

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

as we wanted to show.

$\blacksquare$

## 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.

## Sources

- 1958: Martin Davis:
*Computability and Unsolvability*... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $12$ - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences: Theorem $5$