The Chinese Remainder Theorem

The Chinese Remainder Theorem

Thesis

The Chinese Remainder Theorem (CRT) says that if moduli \(m_1,\ldots,m_k\) are pairwise coprime, the system \(x \equiv a_i \pmod{m_i}\) has a unique solution modulo \(M = m_1\cdots m_k\). It is the algebraic engine behind secret sharing fragments, some RSA optimisations, and calendar problems.

Mental model

  x ≡ a1 (mod m1)
  x ≡ a2 (mod m2)
  …
  Mi = M / mi,  yi = Mi^{-1} mod mi
  x = Σ ai Mi yi  (mod M)

Pairwise coprime ⇒ each \(M_i\) is invertible mod \(m_i\).

Worked example

Solve \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\).

# crt.py
def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

def inv(a, m):
    g, x, _ = egcd(a, m)
    assert g == 1
    return x % m

def crt(rems, mods):
    M = 1
    for m in mods:
        M *= m
    x = 0
    for a, m in zip(rems, mods):
        Mi = M // m
        x += a * Mi * inv(Mi, m)
    return x % M, M

x, M = crt([2, 3, 2], [3, 5, 7])
print(f"x={x} mod {M}; checks", x % 3, x % 5, x % 7)

x=23 mod 105; checks 2 3 2

So \(x = 23\) works: \(23 = 7\cdot 3 + 2\), \(23 = 4\cdot 5 + 3\), \(23 = 3\cdot 7 + 2\), and solutions repeat every \(105\).

Trap

Applying the formula when moduli share a factor. If \(\gcd(m_i,m_j) \neq 1\), a solution may not exist (inconsistent remainders) or uniqueness fails. Always check coprimality or use the general simultaneous-congruence algorithm.

Boring rule

For pairwise-coprime moduli, compute \(M\), each \(M_i\), each inverse, sum, reduce mod \(M\). Verify by evaluating \(x \bmod m_i\).

Try this

1. Change the third remainder to \(3\) and watch the assertions fail (or detect inconsistency).
2. Use CRT to merge two digits of a product in a modular multiplication pipeline.
3. Prove uniqueness: if \(x,y\) both work, \(M\) divides \(x-y\).

Sources

• Ireland & Rosen, A Classical Introduction to Modern Number Theory (CRT chapter)
• Any abstract algebra text: \(\mathbb{Z}/M\mathbb{Z} \cong \prod \mathbb{Z}/m_i\mathbb{Z}\)