# Chinese Remainder Theorem/General Result

## Theorem

Let $b_1, b_2, \ldots, b_r \in \Z$.

Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.

Let $\ds N = \prod_{i \mathop = 1}^r n_i$.

Then the system of linear congruences:

\(\ds x\) | \(\equiv\) | \(\ds b_1\) | \(\ds \pmod {n_1}\) | |||||||||||

\(\ds x\) | \(\equiv\) | \(\ds b_2\) | \(\ds \pmod {n_2}\) | |||||||||||

\(\ds \) | \(\vdots\) | \(\ds \) | ||||||||||||

\(\ds x\) | \(\equiv\) | \(\ds b_r\) | \(\ds \pmod {n_r}\) |

has a simultaneous solution which is unique modulo $N$.

### Corollary

Let $n_1, n_2, \ldots, n_r$ be pairwise coprime positive integers.

Let $\ds N = \prod_{i \mathop = 1}^r n_i$.

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

### Existence

Let $N_k = \dfrac N {n_k}$ for $k = 1, 2, \ldots, r$.

From Integer Coprime to all Factors is Coprime to Whole:

- $\forall k \in \set {1, 2, \ldots, r}: \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$

From Solution of Linear Congruence, the linear congruence:

- $N_k x \equiv b_k \pmod {n_k}$

has a unique solution modulo $n_k$.

Let this solution be $x_k$.

That is:

- $(1): \quad N_k x_k \equiv b_k \pmod {n_k}$

for $k = 1, 2, \ldots, r$.

Let $\ds x_0 = \sum_{i \mathop = 1}^r N_i x_i$.

For each $k, i \in \set {1, 2, 3, \ldots, r}$ such that $i \ne k$:

\(\ds n_k\) | \(\divides\) | \(\ds N\) | ||||||||||||

\(\ds \leadsto \ \ \) | \(\ds n_k\) | \(\divides\) | \(\ds n_i N_i\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds n_k\) | \(\divides\) | \(\ds N_i\) | Euclid's Lemma | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds n_k\) | \(\divides\) | \(\ds N_i x_i\) | Divisor Divides Multiple | ||||||||||

\(\text {(2)}: \quad\) | \(\ds \leadsto \ \ \) | \(\ds N_i x_i\) | \(\equiv\) | \(\ds 0\) | \(\ds \pmod {n_k}\) | Congruent to Zero iff Modulo is Divisor |

Then for each $k = 1, 2, 3, \ldots, r$:

\(\ds x_0\) | \(\equiv\) | \(\ds \sum_{i \mathop = 1}^r N_i x_i\) | ||||||||||||

\(\ds \) | \(\equiv\) | \(\ds N_k x_k\) | from $(2)$ | |||||||||||

\(\ds \) | \(\equiv\) | \(\ds b_k\) | \(\ds \pmod {n_k}\) | from $(1)$ |

Thus $x_0$ is a simultaneous solution.

$\Box$

### Uniqueness

Suppose $x'$ is a second solution of the system.

That is:

- $\forall k \in \set {1, 2, \ldots, r}: x_0 \equiv x' \equiv b_k \pmod {n_k}$

Then:

\(\ds \forall k \in \set {1, 2, \ldots, r}: \, \) | \(\ds x'\) | \(\equiv\) | \(\ds x_0\) | \(\ds \pmod {n_k}\) | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \forall k \in \set {1, 2, \ldots, r}: \, \) | \(\ds n_k\) | \(\divides\) | \(\ds x' - x_0\) | Definition of Congruence | |||||||||

\(\ds \leadsto \ \ \) | \(\ds N\) | \(\divides\) | \(\ds x' - x_0\) | All Factors Divide Integer then Whole Divides Integer | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds x'\) | \(\equiv\) | \(\ds x_0\) | \(\ds \pmod N\) | Definition of Congruence |

Thus the simultaneous solution is unique modulo $N$.

$\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

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