The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT)

If the moduli $m_1, m_2, \ldots, m_k$ are pairwise coprime (any two share no common factor), then the system of congruences

$x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}, \quad \ldots, \quad x \equiv a_k \pmod{m_k}$

has a unique solution modulo $M = m_1 \times m_2 \times \cdots \times m_k$.

Step-by-step: Solve the system

$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}$

Step 1 — Check pairwise coprimality. $\gcd(3,5) = 1$, $\gcd(3,7) = 1$, $\gcd(5,7) = 1$. ✓

Step 2 — Compute $M$. $M = 3 \times 5 \times 7 = 105$.

Step 3 — Compute partial products. $M_1 = M/m_1 = 105/3 = 35$, $M_2 = 105/5 = 21$, $M_3 = 105/7 = 15$.

Step 4 — Find modular inverses. We need $M_i^{-1} \pmod{m_i}$ (the number $y_i$ such that $M_i \cdot y_i \equiv 1 \pmod{m_i}$):

$35 y_1 \equiv 1 \pmod{3}$: $35 \equiv 2 \pmod{3}$, and $2 \times 2 = 4 \equiv 1 \pmod{3}$. So $y_1 = 2$.

$21 y_2 \equiv 1 \pmod{5}$: $21 \equiv 1 \pmod{5}$, so $y_2 = 1$.

$15 y_3 \equiv 1 \pmod{7}$: $15 \equiv 1 \pmod{7}$, so $y_3 = 1$.

Step 5 — Combine.

$x = a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3$ $= 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1$ $= 140 + 63 + 30 = 233$

Step 6 — Reduce mod $M$. $233 \mod 105 = 233 - 2 \times 105 = 23$.

$\boxed{x \equiv 23 \pmod{105}}$

Verification: $23 \mod 3 = 2$ ✓, $23 \mod 5 = 3$ ✓, $23 \mod 7 = 2$ ✓.

Intuition: why 23 works

23 is the unique number between 0 and 104 that simultaneously leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. Adding 105 to 23 gives 128, which also satisfies all three — the solution repeats every 105.

Try it in the visualization

Enter the remainders and moduli. The CRT construction is animated step by step. The solution is verified against all congruences. A number line shows the periodic solutions.