# 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](https://en.wikipedia.org/wiki/Coprime_integers) 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](https://en.wikipedia.org/wiki/Modular_arithmetic).

`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](https://en.wikipedia.org/wiki/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:

```python
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](https://en.wikipedia.org/wiki/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.