The Chinese Remainder Theorem
A puzzle from a 3rd-century Chinese text: a number leaves remainder 2 on division by 3,
remainder 3 by 5, and remainder 2 by 7 — what is it? Solving several
congruences at once
looks daunting, but the Chinese Remainder Theorem (CRT) guarantees a unique
answer and tells you how to find it.
The statement
Let n_1, n_2, \dots, n_k be pairwise coprime moduli,
with product N = n_1 n_2 \cdots n_k. Then the system
x \equiv a_1 \!\!\pmod{n_1}, \quad x \equiv a_2 \!\!\pmod{n_2}, \quad \dots, \quad x \equiv a_k \!\!\pmod{n_k}
has exactly one solution modulo N.
"Pairwise coprime" is essential — the moduli must share no factors. Then the
lcm
of the moduli is their full product N, which is the period at which
the combined pattern repeats.
Building the solution
The constructive recipe: for each i, let
N_i = N / n_i (the product of all the other moduli). Since
N_i is coprime to n_i, it has an
inverse
M_i \equiv N_i^{-1} \pmod{n_i}. Then
x \equiv \sum_{i=1}^{k} a_i\, N_i\, M_i \pmod{N}.
Each term is designed to equal a_i modulo
n_i and vanish modulo every other n_j. The
old puzzle comes out to x \equiv 23 \pmod{105}.
The deeper meaning
CRT says a number mod N is completely determined by its
remainders modulo the coprime parts — and any combination of remainders is achievable. In
structural language, it splits one big system into independent small ones:
\mathbb{Z}_{n_1 n_2 \cdots n_k} \;\cong\; \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \cdots \times \mathbb{Z}_{n_k}.
This "divide and conquer" is enormously useful: it speeds up RSA decryption several-fold, underlies
secret-sharing schemes, and lets big modular computations be done in small, parallel pieces.