Chinese Remainder Theorem — Mathematics Knowledge System

Overview

The Chinese remainder theorem (CRT), first recorded by the mathematician Sunzi in the 3rd–5th century CE and generalized in the West by Gauss, says that a system of congruences with pairwise coprime moduli always has a unique solution modulo the product of those moduli. If you know a number's remainder when divided by 3, by 5, and by 7 separately, CRT tells you there is exactly one number modulo 105 = 3·5·7 consistent with all three remainders — and gives an explicit recipe for reconstructing it. This turns 'many small congruences' into 'one congruence mod the product,' which is why CRT underlies fast modular arithmetic in cryptography (RSA decryption is often accelerated by working mod p and mod q separately and recombining), coding theory, and the internal design of computer arithmetic.

Intuition

Picture three interlocking gears with 3, 5, and 7 teeth, each marked at a starting position. As they turn together, the combined pattern of tooth-marks only repeats once every 3·5·7 = 105 turns — before that, every combination of positions is distinct. CRT is the statement that this 'combined pattern' is in one-to-one correspondence with a single number mod 105: knowing where each individual gear points is exactly equivalent to knowing one number in {0, 1, …, 104}.

Formal Definition

Definition

Let n₁, …, nₖ be pairwise coprime positive integers and N = n₁n₂⋯nₖ. For any remainders a₁, …, aₖ, the system of congruences

x \equiv a_1 \pmod{n_1}, \ \ x \equiv a_2 \pmod{n_2}, \ \ \ldots, \ \ x \equiv a_k \pmod{n_k}

System of congruences

\text{has a unique solution } x \pmod{N}, \qquad N = n_1 n_2 \cdots n_k

Existence and uniqueness

x = \sum_{i=1}^{k} a_i \, N_i \, M_i \pmod{N}, \qquad N_i = \tfrac{N}{n_i}, \ \ M_i \equiv N_i^{-1} \!\!\pmod{n_i}

Explicit reconstruction formula

Worked Examples

N = 5·7 = 35. For the mod-5 congruence, N₁ = 35/5 = 7; find M₁ = 7⁻¹ mod 5. Since 7 ≡ 2 (mod 5) and 2·3 = 6 ≡ 1 (mod 5), M₁ = 3.
$N_1 M_1 = 7 \cdot 3 = 21 \equiv 1 \pmod 5$
For the mod-7 congruence, N₂ = 35/7 = 5; find M₂ = 5⁻¹ mod 7. Since 5·3 = 15 ≡ 1 (mod 7), M₂ = 3.
$N_2 M_2 = 5 \cdot 3 = 15 \equiv 1 \pmod 7$
Combine: x ≡ a₁N₁M₁ + a₂N₂M₂ = 2·21 + 3·15 = 42 + 45 = 87 ≡ 87 − 2·35 = 17 (mod 35).
$x \equiv 2\cdot 21 + 3 \cdot 15 = 87 \equiv 17 \pmod{35}$

Answer: x ≡ 17 (mod 35). Check: 17 mod 5 = 2 ✓, 17 mod 7 = 3 ✓.

Practice Problems

Difficulty 2/10

Compute 17 mod 7.

Difficulty 6/10

Find x (mod 105) satisfying x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

Difficulty 5/10

Why does the standard CRT reconstruction not directly apply to the system x ≡ 1 (mod 4), x ≡ 3 (mod 6)?

Quiz

Summary

For pairwise coprime moduli n₁,…,nₖ, a system of congruences x ≡ aᵢ (mod nᵢ) has a unique solution modulo N = n₁n₂⋯nₖ.
The solution is reconstructed explicitly via x ≡ Σ aᵢNᵢMᵢ (mod N), where Nᵢ = N/nᵢ and Mᵢ = Nᵢ⁻¹ mod nᵢ.
CRT converts several small congruences into one large one, and underlies fast modular exponentiation (e.g. accelerated RSA decryption).

References

WebsiteWikipedia — Chinese remainder theorem