Chinese Remainder Theorem — System of Modular Equations

The Chinese Remainder Theorem appears in a 3rd century AD Chinese mathematical text with the problem: 'A number gives remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. What is the number?' (Answer: 23). The theorem's 1700-year journey from recreational mathematics to RSA optimisation is one of the better stories in applied mathematics.

In production RSA, CRT speeds up decryption by roughly 4x. Instead of one computation modulo n (a 2048-bit number), you do two computations modulo p and q (each ~1024 bits), then combine with CRT. Since modular exponentiation is O(log e × log^2 n) in the number of bit operations, halving the number size reduces each operation by ~4x.

The Theorem and Constructive Proof

Given pairwise coprime m1,...,mk and remainders a1,...,ak, the unique solution mod M=Πmi is: x = Σ ai × Mi × yi mod M where Mi = M/mi and yi = Mi^(-1) mod mi.

from math import gcd
from functools import reduce

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def crt(remainders: list[int], moduli: list[int]) -> int:
    """
    Solve x ≡ remainders[i] (mod moduli[i]) for all i.
    Moduli must be pairwise coprime.
    Returns x mod M where M = product of all moduli.
    """
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for ai, mi in zip(remainders, moduli):
        Mi = M // mi
        _, yi, _ = extended_gcd(Mi, mi)  # Mi * yi ≡ 1 (mod mi)
        x += ai * Mi * yi
    return x % M

# x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(crt([2, 3, 2], [3, 5, 7]))  # 23
# Verify
print(23 % 3, 23 % 5, 23 % 7)    # 2 3 2 ✓

CRT for Two Congruences

The two-equation version appears frequently — merge two congruences into one.

def crt_two(a1, m1, a2, m2):
    """Solve x ≡ a1 (mod m1) and x ≡ a2 (mod m2).
    Works even if gcd(m1,m2) != 1 (if solution exists).
    Returns (x, lcm) or None if no solution.
    """
    g = gcd(m1, m2)
    if (a2 - a1) % g != 0:
        return None  # no solution
    lcm = m1 * m2 // g
    _, p, _ = extended_gcd(m1 // g, m2 // g)
    x = (a1 + m1 * ((a2 - a1) // g * p % (m2 // g))) % lcm
    return x, lcm

print(crt_two(0, 3, 3, 4))  # (3, 12) → x≡3 (mod 12)
print(crt_two(1, 6, 3, 4))  # None — no solution (1 is odd but 3 is odd too... let's check)
print(crt_two(2, 6, 3, 4))  # None — no solution

Applications

RSA speed-up: Chinese Remainder Theorem speeds up RSA decryption by ~4x — decrypt with p and q separately, then combine.

Calendar problems: 'A week has 7 days, a month ~30 days. What day of the week will 1 January be in year Y?' — CRT-style reasoning.

Competitive programming: Problems of the form 'find n such that n mod a1=r1 and n mod a2=r2...' are direct CRT applications.

Hash functions: CRT enables working with small moduli for speed, then combining for correctness.

Frequently Asked Questions