Chinese Remainder Theorem Simplified

The Chinese Remainder Theorem (CRT) sounds fancy but it is one of the most concrete and useful results in elementary number theory: it explains how a number can be completely described by its remainders when divided by several pairwise-coprime moduli, and it gives an explicit, efficient recipe to reconstruct that number.

Imagine the problem like this: someone hides a number and gives you a few clues — its remainder when divided by 3, by 5, by 7, and so on. If the numbers (3, 5, 7, ...) are pairwise coprime (no two have a common factor greater than 1), these clues together uniquely determine the hidden number, except for adding multiples of the product of these numbers.

Giving the remainders for each factor is the same as giving the remainder for the product. This idea is not only neat but also very useful. It lets you break down big modular calculations into smaller, easier, and faster ones, which can be done in parallel. Then, you can combine the results using a simple, low-cost method.

Understanding CRT begins with the intuition of “matching residues” and ends with a handful of reliable computational tools — the product N of the moduli, the partial products Nᵢ = N / nᵢ, and the modular inverses of those partial products modulo each corresponding modulus — and once you grasp why those pieces fit together, everything else (examples, edge cases, optimizations) becomes straightforward.

To see the theorem in its simplest form, consider two coprime integers p and q. The two-modulus CRT states: for any pair of residues a (mod p) and b (mod q) there exists a unique x modulo N = p·q such that x ≡ a (mod p) and x ≡ b (mod q).

The constructive proof gives us the algorithm: compute N = p·q, set N₁ = N/p and N₂ = N/q; find integers y₁ and y₂ so that N₁·y₁ ≡ 1 (mod p) and N₂·y₂ ≡ 1 (mod q) — these y’s are modular inverses and can be computed efficiently using the extended Euclidean algorithm — and then the number x = a·N₁·y₁ + b·N₂·y₂ (reduced modulo N) satisfies both congruences.

N₁ is divisible by q and so contributes 0 (mod q) while N₁·y₁ ≡ 1 (mod p) gives the needed a (mod p); symmetrically N₂ contributes 0 (mod p) and 1 (mod q). Uniqueness follows because if two numbers agree modulo both p and q then their difference is divisible by both p and q; since p and q are coprime their product divides the difference, so they are the same modulo N. This same construction extends to any finite list of pairwise-coprime moduli n₁, n₂, …, n_k: compute N = ∏ nᵢ, compute Nᵢ = N / nᵢ for every i, compute yᵢ = (Nᵢ)^{-1} mod nᵢ, and set x ≡ Σ aᵢ·Nᵢ·yᵢ (mod N). The extended Euclidean algorithm gives every modular inverse efficiently; conceptually you only need to know that an inverse exists because gcd(Nᵢ, nᵢ) = 1 when the moduli are pairwise coprime.

To make this concrete, walk through examples carefully and check arithmetic as you go: solve x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Here N = 15, N₁ = 5, N₂ = 3. Find y₁ with 5·y₁ ≡ 1 (mod 3): since 5 ≡ 2 (mod 3) and 2·2 ≡ 1 (mod 3), y₁ = 2. Find y₂ with 3·y₂ ≡ 1 (mod 5): 3·2 = 6 ≡ 1 (mod 5), so y₂ = 2. Then x = 2·5·2 + 3·3·2 = 20 + 18 = 38 ≡ 8 (mod 15), and indeed 8 ≡ 2 (mod 3) and 8 ≡ 3 (mod 5).

The CRT construction is mechanical and scales: for three or more moduli you do the same for each index and sum all contributions, reducing modulo N at the end (or along the way to keep numbers small). A useful operational detail for programmers is always to reduce aᵢ modulo nᵢ before combining, and to compute the Nᵢ and yᵢ once when you perform many reconstructions (precompute and cache them). For extremely large moduli use big-integer libraries; for repeated conversions between the direct-product (CRT) representation and the canonical single-modulus representation the little precomputation (Nᵢ and yᵢ) reduces every conversion to k multiplications and one modular reduction, which is fast.

Because the CRT is constructive, it turns into straightforward, reliable code. The modular inverse function is implemented with the extended Euclidean algorithm; once you have modinv you implement CRT by multiplying out N and combining the aᵢ·Nᵢ·modinv(Nᵢ, nᵢ) terms. Here is a compact, safe Python implementation you can drop into a utility module:

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

def modinv(a, m):
    x, y, g = extended_gcd(a, m)
    if g != 1:
        raise ValueError("Inverse does not exist (not coprime)")
    return x % m

def crt(pairs):
    """
    pairs: list of (ai, ni) with ni pairwise coprime.
    Returns (x, N) where x is the smallest nonnegative solution modulo N = product(ni).
    """
    N = 1
    for _, n in pairs:
        N *= n
    total = 0
    for a, n in pairs:
        a = a % n
        Ni = N // n
        yi = modinv(Ni, n)
        total += a * Ni * yi
    return (total % N, N)

This code is robust for educational and moderate production uses; for cryptographic workloads prefer vetted libraries and big-int implementations that include timing-attack mitigations.

In conclusion, the Chinese Remainder Theorem is a concrete, practical bridge between theory and computation: it tells you that a number modulo a large product can be represented exactly by its residues modulo each pairwise-coprime factor, and it gives a simple, deterministic recipe to reconstruct that number using partial products and modular inverses. This means CRT turns intimidating large-modulus problems into many small, independent tasks that are easier to reason about, implement, and even parallelize; for practitioners it offers real speedups (notably in RSA private-key operations) and a convenient representation that can be precomputed and reused when you convert many times.