Chinese Remainder Theorem

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences. Given:

$x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$

when $\gcd(m_1, m_2) = 1$, there is a unique solution $x$ modulo $m_1 m_2$.

Historical Context

The theorem is named after the "Mathematical Classic of Sun Zi" (4th century AD), which posed: "We have things of which we do not know the number; if we count them by threes, we have two left over; by fives, we have three left over; by sevens, we have two left over. How many things are there?"

Solving with Extended GCD

Using Bezout's identity: find $s, t$ such that $m_1 s + m_2 t = 1$ (using extended GCD). Then:

$x = a_1 m_2 t + a_2 m_1 s \pmod{m_1 m_2}$

Equivalently, we can write it as:

$x = a_1 + m_1 \cdot s \cdot (a_2 - a_1) \pmod{m_1 m_2}$

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

def crt(a1, m1, a2, m2):
    g, s, t = extended_gcd(m1, m2)
    modulus = m1 * m2 // g
    x = (a1 + m1 * s * (a2 - a1) // g) % modulus
    return x

# x ≡ 2 (mod 3), x ≡ 3 (mod 5) → x = 8
print(crt(2, 3, 3, 5))   # 8
# Verify: 8 % 3 = 2 ✓, 8 % 5 = 3 ✓

Verification

Always verify: if x = crt(a1, m1, a2, m2) then x % m1 == a1 and x % m2 == a2.

Generalization

CRT extends to any number of congruences, applying the two-congruence version iteratively. It also works when $\gcd(m_1, m_2) \neq 1$, but only if $\gcd(m_1, m_2) \mid (a_2 - a_1)$.

Your Task

Using an extended_gcd helper provided in the starter code, implement crt(a1, m1, a2, m2) that returns the unique $x \in [0, m_1 m_2)$ satisfying both congruences.