The Chinese Remainder Theorem

An old puzzle from the Chinese mathematician Sunzi asks for a number with given remainders on division by 3, by 5 and by 7. Systems like this are everywhere in modern number theory and computing: a number can be stored by its remainders mod a few coprime moduli, and the Chinese Remainder Theorem (CRT) says nothing is lost. It is built from modular inverses.

Theorem. If $\gcd(m, n) = 1$, then for any $a$ and $b$ the system $$x \equiv a \pmod{m}, \qquad x \equiv b \pmod{n}$$ has a solution, and any two solutions are congruent mod $mn$. So there is exactly one solution mod $mn$.

Why it works

Existence. The first congruence says $x = a + mk$. Put that into the second: $mk \equiv b - a \pmod{n}$. Since $\gcd(m, n) = 1$, $m$ has an inverse mod $n$, so $k \equiv (b - a)\,m^{-1} \pmod{n}$ works. Uniqueness. If $x$ and $x'$ both solve the system, then $m \mid x - x'$ and $n \mid x - x'$. Coprime numbers that both divide something divide it together (no prime is shared), so $mn \mid x - x'$.

Rows are remainders mod 4, columns remainders mod 5. Each number goes one row down and one column right. Since $\gcd(4, 5) = 1$, the numbers $0$ to $19$ fill all 20 cells exactly once; the marked cell, $x \equiv 1 \pmod{4}$ and $x \equiv 3 \pmod{5}$, holds 13.

Worked example: Two congruences

Solve $x \equiv 2 \pmod{5}$ and $x \equiv 3 \pmod{7}$.

$x = 2 + 5k$. Then $2 + 5k \equiv 3 \pmod{7}$, so $5k \equiv 1 \pmod{7}$.
$5^{-1} \equiv 3 \pmod{7}$ (since $15 \equiv 1$), so $k \equiv 3$, and $x = 2 + 15 = 17$.
Check: $17 = 3 \cdot 5 + 2$ and $17 = 2 \cdot 7 + 3$. All solutions: $x \equiv 17 \pmod{35}$.

Answer: $x \equiv 17 \pmod{35}$.

Worked example: Three congruences

Find the smallest $x \ge 0$ with $x \equiv 1 \pmod{3}$, $x \equiv 2 \pmod{4}$, $x \equiv 3 \pmod{5}$.

Combine the first two: $x = 1 + 3k$, $3k \equiv 1 \pmod{4}$, $k \equiv 3$, so $x \equiv 10 \pmod{12}$.
Combine with the third: $x = 10 + 12j$, $12j \equiv -7 \pmod{5}$, that is $2j \equiv 3$, so $j \equiv 4$ and $x = 58$.
Check: $58 = 3 \cdot 19 + 1 = 4 \cdot 14 + 2 = 5 \cdot 11 + 3$.

Answer: $x = 58$ (unique mod $60$).

With $\gcd(4, 6) = 2$ the path closes after $\operatorname{lcm}(4, 6) = 12$ steps, so half the cells stay empty. The marked cell asks for $x \equiv 1 \pmod{4}$ (odd) and $x \equiv 2 \pmod{6}$ (even): impossible.

Worked example: Moduli with a common factor

Solve $x \equiv 1 \pmod{4}$, $x \equiv 3 \pmod{6}$, giving all $x$ with $0 \le x < 24$.

$\gcd(4, 6) = 2$, so both congruences say something mod 2: $x$ is odd and $x$ is odd. They agree, so there are solutions.
Try odd numbers $\equiv 1 \pmod{4}$: $1, 5, 9$. $9 \equiv 3 \pmod{6}$, so $x \equiv 9 \pmod{12}$, the lcm.
Below 24: $x = 9$ and $x = 21$, two solutions mod 24 rather than one.

Answer: $x = 9$ or $21$.

Common mistake

Using the theorem when the moduli share a factor. Then there may be no solution ($x \equiv 1 \pmod{4}$ and $x \equiv 2 \pmod{6}$ disagree about parity) or several mod $mn$. Check $\gcd(m, n)$ first; if it is $d > 1$, the system is solvable exactly when $a \equiv b \pmod{d}$, and then the solution is unique mod $\operatorname{lcm}(m, n)$.

Key idea

For coprime moduli, $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$ have exactly one solution mod $mn$: write $x = a + mk$ and solve for $k$ with $m^{-1} \bmod n$.

The Chinese Remainder Theorem

Practice

Builds on

Leads to

Sources and further reading