Chinese Remainder Theorem Algorithm Tutorial

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory. It states that if you know the remainders of an integer when divided by several pairwise coprime numbers, you can uniquely determine the remainder when divided by their product.

Historical context: The theorem appears in the 3rd century Chinese text Sunzi Suanjing, where it was used to solve problems about counting soldiers.

Problem statement: Given a system of congruences: $x \equiv a_1 \pmod{m_1}$ $x \equiv a_2 \pmod{m_2}$ $\vdots$ $x \equiv a_n \pmod{m_n}$

where $\gcd(m_i, m_j) = 1$ for all $i \ne j$, there exists a unique solution modulo $M = m_1 \cdot m_2 \cdot \ldots \cdot m_n$.

The classical CRT proof gives an explicit formula for the solution.

Setup:

• Let $M = m_1 \cdot m_2 \cdot \ldots \cdot m_n$
• Let $M_i = M / m_i$ (product of all moduli except $m_i$)
• Let $y_i = M_i^{-1} \pmod{m_i}$ (modular inverse of $M_i$ mod $m_i$)

The solution: $x = \sum_{i=1}^{n} a_i \cdot M_i \cdot y_i \pmod{M}$

Why it works:

• $M_i \cdot y_i \equiv 1 \pmod{m_i}$
• $M_i \cdot y_i \equiv 0 \pmod{m_j}$ for $j \ne i$ (since $m_j | M_i$)

So the $i$-th term contributes $a_i$ modulo $m_i$ and 0 modulo all other $m_j$.

A simpler approach combines equations one at a time.

Algorithm:

function solve_crt(equations):
    x = equations[0].remainder
    mod = equations[0].modulus

    for each (a, m) in equations[1:]:
        // Find k such that: x + k * mod ≡ a (mod m)
        // k ≡ (a - x) * mod^(-1) (mod m)
        inv = modular_inverse(mod, m)
        k = ((a - x) * inv) mod m
        if k < 0: k += m

        x = x + k * mod
        mod = mod * m
        x = x mod mod

    return x

Why it works: After processing the first $i$ equations, $x$ satisfies all of them modulo $\text{lcm}(m_1, \ldots, m_i)$. Since all moduli are coprime, this LCM is just their product.

To find the modular inverse, we use the Extended Euclidean Algorithm.

Extended GCD: Given $a$ and $b$, find $x, y$ such that $ax + by = \gcd(a, b)$.

function extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)

    (g, x, y) = extended_gcd(b, a mod b)
    return (g, y, x - (a / b) * y)

Modular inverse: If $\gcd(a, m) = 1$, then: $ax + my = 1$ $ax \equiv 1 \pmod{m}$

So $x$ (reduced mod $m$) is the modular inverse of $a$ mod $m$.

function modular_inverse(a, m):
    (g, x, _) = extended_gcd(a, m)
    if g != 1: error("No inverse")
    return ((x mod m) + m) mod m