The Chinese Remainder Theorem

The puzzle, and why one answer always fits

A 1,700-year-old riddle, from the Chinese text Sunzi Suanjing: there are things whose number is unknown. Counted by threes the remainder is 2, by fives the remainder is 3, by sevens the remainder is 2. How many things? The answer is 23 — and the Chinese Remainder Theorem is the statement that 23 is the only answer in the range 0 to 104, the next being 128, then 233, each exactly 105 = 3 × 5 × 7 apart.

That is the whole idea. Pick divisors that share no common factor — 3, 5, 7. Any whole number leaves a remainder against each one, and the list of those remainders behaves like a fingerprint. The theorem guarantees the fingerprint is unique below the product of the divisors, and that you can run the lift backwards: given the remainders, recover the single number that produced them. The remainder list (2, 3, 2) and the number 23 are two encodings of the same thing.

The reason it works is counting. There are exactly N = n₁·n₂·…·n_k tuples of remainders, and exactly N numbers in the range 0 to N−1. The map from numbers to tuples is a function; coprimality forces it to be injective; a one-to-one map between two finite sets of equal size is a bijection. So every tuple is hit by exactly one number — existence and uniqueness at once.

The mechanism: lifting remainders back to a number

We want the smallest non-negative x solving the system

x ≡ r₁  (mod n₁)
x ≡ r₂  (mod n₂)
   ⋮
x ≡ r_k (mod n_k)

Let N = n₁·n₂·…·n_k. The classical Gauss construction builds one "basis" number per congruence that is 1 mod its own modulus and 0 mod every other, then scales and sums:

For each i:
  Nᵢ   = N / nᵢ                       // product of the OTHER moduli
  Mᵢ   = Nᵢ⁻¹ (mod nᵢ)               // modular inverse of Nᵢ modulo nᵢ
                                       //   (exists because gcd(Nᵢ, nᵢ) = 1)
x = ( Σ rᵢ · Nᵢ · Mᵢ ) mod N

Each term Nᵢ·Mᵢ is divisible by every modulus except nᵢ (so it vanishes there) and equals 1 modulo nᵢ (by construction of the inverse). Multiplying by rᵢ turns it into a term that contributes exactly rᵢ to the i-th coordinate and nothing elsewhere. Summing assembles all coordinates without interference. The modular inverses come from the extended Euclidean algorithm, which for coprime a, n returns integers s, t with a·s + n·t = 1, so s = a⁻¹ (mod n).

The complexity has two parts. Setting up the k inverses costs O(k log N) bit operations via extended Euclid. Once they exist, each reconstruction is k modular multiply-adds — O(k) machine operations if every modulus fits in a CPU word, or O(k²) bit operations on true big integers because the running sum grows to the full width of N. The inverses depend only on the moduli, so across many reconstructions with the same divisors the setup is paid once and amortizes away.

When to reach for CRT

• RSA decryption. Decrypting mod a 2048-bit modulus pq is replaced by two exponentiations mod the 1024-bit primes p and q, then a CRT merge. Modular exponentiation is roughly cubic in the bit length, so halving the operand width is the bulk of a 3–4× speedup.
• Residue number systems. Represent one huge integer as its residues against many small word-sized primes. Addition and multiplication become independent, embarrassingly parallel per-residue operations with no carry propagation; CRT reconstructs the true value only at the end.
• Big-integer multiplication and the NTT. Number-theoretic transforms run modulo several CPU-friendly primes to dodge overflow, then CRT-merge the partial products back into the full result.
• Secret sharing and parallel hashing. A value can be split into residues that individually reveal nothing about it until enough are recombined.

Reach for it whenever a problem mod a large composite splits cleanly into smaller coprime pieces, and the per-piece work is much cheaper than the whole. If your modulus is prime, or doesn't factor into coprime parts, CRT buys you nothing — there is nothing to split.

CRT reconstruction methods compared

	Gauss / textbook formula	Garner's algorithm	Iterative pairwise merge	Brute-force search
Reconstruction cost	O(k) mults, O(k²) bit ops	O(k) mults, O(k²) bit ops	O(k) merges	O(N) — exponential in bits
Inverse setup	O(k log N), inverses mod nᵢ of N/nᵢ	O(k²) small inverses mod nᵢ	O(k log N) extended Euclid per merge	none
Widest intermediate value	full product N (every term × N/nᵢ)	single modulus nᵢ until final eval	grows to running LCM	N
Big-integer arithmetic needed	throughout the sum	only at the final mixed-radix evaluation	at each merge step	throughout
Handles non-coprime moduli	no	no (needs coprime)	yes — gcd consistency check built in	yes
Best for	fixed small k, clarity	RNS / many-prime crypto	streaming moduli, generalized CRT	never (teaching only)

The headline trade-off is how wide the intermediate values get. The textbook formula multiplies every term by N/nᵢ, forcing full-width big-integer arithmetic across the entire sum. Garner's algorithm keeps every inverse small — taken modulo a single nᵢ — and defers the only full-width work to a single final evaluation, which is why production crypto libraries use it.

What the numbers actually say

• Uniqueness is exact, not approximate. With moduli 3, 5, 7 there are exactly 105 numbers in range and 105 remainder tuples. The original Sunzi answer 23 repeats every 105: 23, 128, 233, 338, …
• RSA-CRT is about 3–4× faster. Modular exponentiation cost scales roughly as the cube of the bit length. Two 1024-bit exponentiations cost about 2 × (1/2)³ = 1/4 of one 2048-bit exponentiation in the dominant term; real implementations land near 3–4× after accounting for the CRT merge and per-half overhead.
• RNS removes carry propagation. Adding two 4096-bit numbers normally chains carries across 64 machine words. Split across 64 coprime word-sized moduli, the 64 residue additions are fully independent — ideal for SIMD or GPU lanes.
• Inverses amortize. The k modular inverses depend only on the moduli, not the data. Decrypt a million RSA messages with the same key and you compute the CRT inverses exactly once at key generation.
• Brute force is hopeless. Scanning 0…N−1 for a match is O(N) — exponential in the bit length of N. For a 2048-bit RSA modulus that is on the order of 2²⁰⁴⁸ candidates; the algebraic reconstruction does it in a few dozen big-integer multiplications.

JavaScript implementation

Using BigInt so the arithmetic stays exact for cryptographic-size moduli. The extended Euclidean algorithm supplies the modular inverses, and we run the Gauss formula:

// extended gcd: returns [g, s, t] with a*s + b*t = g = gcd(a, b)
function egcd(a, b) {
  if (b === 0n) return [a, 1n, 0n];
  const [g, s, t] = egcd(b, a % b);
  return [g, t, s - (a / b) * t];
}

// modular inverse of a modulo m (m > 0), or null if it doesn't exist
function modInverse(a, m) {
  const [g, x] = egcd(((a % m) + m) % m, m);
  if (g !== 1n) return null;          // not coprime → no inverse
  return ((x % m) + m) % m;
}

// Solve x ≡ r[i] (mod n[i]) for pairwise-coprime n[i].
// Returns the unique x in [0, N) where N = product(n).
function crt(r, n) {
  const N = n.reduce((a, b) => a * b, 1n);
  let x = 0n;
  for (let i = 0; i < n.length; i++) {
    const Ni = N / n[i];              // product of the other moduli
    const Mi = modInverse(Ni, n[i]);  // Ni⁻¹ (mod n[i])
    if (Mi === null) throw new Error('moduli are not pairwise coprime');
    x = (x + r[i] * Ni * Mi) % N;
  }
  return ((x % N) + N) % N;
}

// Sunzi's riddle: x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7)
console.log(crt([2n, 3n, 2n], [3n, 5n, 7n]).toString());  // "23"

Two details worth flagging. First, every modular inverse is normalized back into [0, m) with ((x % m) + m) % m because JavaScript's % returns a negative result for negative operands. Second, a null inverse is the early-warning that the moduli aren't coprime — handle it rather than producing a silently wrong answer.

Python implementation — and Garner's algorithm

Python's integers are arbitrary precision, so no special big-int type is needed, and pow(a, -1, m) (Python 3.8+) gives the modular inverse directly. Below: the same Gauss formula, then Garner's algorithm, which is the version production code actually ships because it keeps every inverse small.

from math import prod

def crt(r, n):
    """Gauss construction. n must be pairwise coprime."""
    N = prod(n)
    x = 0
    for ri, ni in zip(r, n):
        Ni = N // ni
        Mi = pow(Ni, -1, ni)        # Ni^-1 mod ni, raises if not coprime
        x = (x + ri * Ni * Mi) % N
    return x % N

def crt_garner(r, n):
    """Garner's algorithm — mixed-radix reconstruction.
    Every inverse is taken modulo a single small n[i]."""
    x = r[0] % n[0]                  # first mixed-radix digit
    radix = 1                        # running product n[0]*...*n[i-1]
    for i in range(1, len(n)):
        radix *= n[i - 1]
        inv = pow(radix, -1, n[i])   # inverse of the running radix mod n[i]
        digit = (r[i] - x) * inv % n[i]   # peel off everything already placed
        x += digit * radix           # the ONLY full-width arithmetic
    return x

print(crt([2, 3, 2], [3, 5, 7]))         # 23
print(crt_garner([2, 3, 2], [3, 5, 7]))  # 23

The contrast is the point. The Gauss formula multiplies each term by N // ni, a number nearly as wide as the whole product. Garner builds the answer digit by digit in a mixed-radix base (n₀, n₀n₁, n₀n₁n₂, …), so every inverse and every % nᵢ stays modulo a single small modulus; the only full-width arithmetic is the running x += digit · radix accumulation.

Variants worth knowing

Generalized (non-coprime) CRT. When moduli share factors, a solution exists if and only if every pair agrees on the shared part: rᵢ ≡ rⱼ (mod gcd(nᵢ, nⱼ)). When it exists, the answer is unique modulo the least common multiple of the moduli, not their product. The merge step uses extended Euclid to both test consistency and combine the pair.

Iterative pairwise merge. Instead of the closed formula, fold the congruences two at a time: merge (r₁, n₁) and (r₂, n₂) into a single congruence mod lcm(n₁, n₂), then merge that with the next. This streams over moduli arriving one at a time and naturally accommodates the non-coprime case.

Residue number system (RNS) arithmetic. Don't reconstruct at all until forced to. Keep numbers as residue tuples and do all arithmetic per-coordinate — addition, subtraction, and multiplication are carry-free and parallel. CRT is only invoked at the boundary where a true integer value must be recovered.

Hensel lifting / prime powers. CRT reduces a problem mod p^a · q^b to separate problems mod p^a and q^b; Hensel's lemma then lifts a solution mod p up to mod p^a. The pair is the standard route for solving polynomial congruences over composite moduli.

Common bugs and edge cases

• Non-coprime moduli used blindly. The classic formula needs each Nᵢ to be invertible mod nᵢ. If two moduli share a factor the inverse doesn't exist; detect the missing inverse instead of dividing by an undefined value.
• Overflow in fixed-width languages. The product N and the term rᵢ·Nᵢ·Mᵢ can overflow 64-bit integers fast. Use big integers, or compute the product with 128-bit multiply / __int128 / mulmod.
• Negative remainders from the language's modulo. C, Java, and JavaScript return a negative result when the dividend is negative. Normalize every remainder and inverse to [0, m) before using it.
• Confusing the LCM and product cases. With coprime moduli the period is the product; with shared factors it's the LCM. Reporting the wrong period gives you spurious extra "solutions" or misses real ones.
• Forgetting setup amortization. Recomputing the modular inverses on every reconstruction is wasteful when the moduli are fixed (as in RSA-CRT). Precompute once and cache.
• Off-by-one on the canonical range. The unique solution lives in [0, N). A stray x % N that can return negative, or returning N itself, breaks downstream equality checks.