Chinese remainder theorem

Statement

Let $n_1, \dots, n_k$ be positive integers that are pairwise coprime, and let $N = n_1 n_2 \cdots n_k$. Let $a_1, \dots, a_k$ be integers. Then there is an integer $x$ such that $x \equiv a_i \pmod{n_i}$ for each $i$. Two such integers are congruent modulo $N$.

Remarks

In the language of rings, the map $\mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$, $\overline{x} \mapsto (\overline{x}, \dots, \overline{x})$, is a ring isomorphism. For two moduli $m$ and $n$, write $m u + n v = 1$ with Bézout's identity. Then $x = a_2 m u + a_1 n v$ solves $x \equiv a_1 \pmod m$ and $x \equiv a_2 \pmod n$. The Chinese remainder theorem for non-coprime moduli removes the hypothesis of coprimality.

History

The Chinese book Sunzi Suanjing, from the 5th century, contains the oldest known example of the problem. Qin Jiushao gave a complete method in 1247.

Explanations

L1 human

Find a number that leaves the remainder $2$ when you divide by $3$, the remainder $3$ by $5$, and the remainder $2$ by $7$. The theorem says that such a number exists, and that it is unique up to multiples of $3 \cdot 5 \cdot 7 = 105$. The smallest positive answer is $23$.