Chinese Remainder Theorem

The statement

Suppose m₁, m₂, ..., m_k are positive integers, pairwise coprime — meaning gcd(m_i, m_j) = 1 for every i ≠ j. Then for any integers a₁, a₂, ..., a_k, the system of congruences

x ≡ a_1  (mod m_1)
x ≡ a_2  (mod m_2)
   ⋮
x ≡ a_k  (mod m_k)

has a unique solution x modulo M = m₁ · m₂ · ... · m_k.

"Unique mod M" means: there is exactly one residue class in {0, 1, ..., M − 1} satisfying all the congruences, and any solution shifted by a multiple of M is also a solution. Concretely, exactly one of the M residues makes the whole system work; the rest fail at least one of the congruences.

Equivalently, the map ℤ/M → (ℤ/m_1) × (ℤ/m_2) × ... × (ℤ/m_k) sending x to its tuple of residues is a ring isomorphism. Add, subtract or multiply componentwise on the right, and the result corresponds to add/subtract/multiply on the left.

The constructive proof

To build the solution explicitly:

1. Compute M = m₁ · m₂ · ... · m_k.
2. For each i, compute M_i = M / m_i — the product of all moduli except m_i.
3. For each i, compute y_i = M_i^(−1) mod m_i, the modular inverse. This exists because gcd(M_i, m_i) = 1: every prime factor of M_i comes from some m_j with j ≠ i, and pairwise coprimality means none of those share a factor with m_i. The extended Euclidean algorithm produces y_i in O(log m_i) operations.
4. The solution is x = Σ_{i=1..k} a_i · M_i · y_i (mod M).

Why this works: M_i ≡ 0 (mod m_j) for every j ≠ i, because m_j divides M_i. So when you reduce x mod m_i, every term except the i-th vanishes, leaving

x mod m_i = a_i · M_i · y_i mod m_i
          = a_i · (M_i · y_i) mod m_i
          = a_i · 1 mod m_i
          = a_i

which is exactly what was required. Uniqueness follows because if x and x' both solve the system, their difference is divisible by every m_i, hence by M, hence x ≡ x' (mod M).

Worked example: Sun Tzu's puzzle

The original 4th-century formulation: an unknown number of soldiers, counted in groups of 3 leaves a remainder of 2; in groups of 5 leaves 3; in groups of 7 leaves 2. How many soldiers (modulo 3 × 5 × 7 = 105)?

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Build the solution via CRT:

M = 3 × 5 × 7 = 105

M_1 = 105 / 3 = 35      Want y_1 = 35^(−1) mod 3
                         35 mod 3 = 2, and 2 × 2 = 4 ≡ 1 (mod 3)
                         So y_1 = 2.

M_2 = 105 / 5 = 21      Want y_2 = 21^(−1) mod 5
                         21 mod 5 = 1, so y_2 = 1.

M_3 = 105 / 7 = 15      Want y_3 = 15^(−1) mod 7
                         15 mod 7 = 1, so y_3 = 1.

x = 2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1
  = 140 + 63 + 30
  = 233
  = 233 − 2 × 105
  = 23 (mod 105)

Verify: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓. So Sun Tzu's army has 23, 128, 233, 338, ... soldiers. The 4th-century Chinese commentary gives exactly this answer, derived through a less systematic but equivalent recipe.

The iterative approach

An alternative, easier-to-implement form solves two congruences at a time, then merges. Starting with x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂):

x = a_1 + m_1 · t  for some integer t

Substitute into second: a_1 + m_1 · t ≡ a_2 (mod m_2)
                       m_1 · t ≡ a_2 − a_1 (mod m_2)
                       t ≡ (a_2 − a_1) · m_1^(−1) (mod m_2)

So x ≡ a_1 + m_1 · ((a_2 − a_1) · m_1^(−1) mod m_2) (mod m_1 · m_2)

Then merge that result with the third congruence and so on. This iterative form is what most software libraries (GMP, Sage, Mathematica) actually implement. It's easier to handle non-coprime moduli with this approach: at each merge step, check that (a_2 − a_1) is divisible by gcd(m_1, m_2); if so, the merged modulus becomes lcm(m_1, m_2) instead of the product.

Generalisation to non-coprime moduli

If the moduli are not pairwise coprime, the system may or may not be solvable. The condition: for every pair (i, j), the congruences x ≡ a_i (mod m_i) and x ≡ a_j (mod m_j) must agree on the gcd:

a_i ≡ a_j (mod gcd(m_i, m_j))

If this holds for every pair, the system has a unique solution modulo the lcm of the moduli, lcm(m_1, m_2, ..., m_k). If it fails for any pair, no solution exists.

Example of inconsistent system: x ≡ 1 (mod 4) and x ≡ 2 (mod 6). Here gcd(4, 6) = 2, but 1 mod 2 = 1 and 2 mod 2 = 0; the system is inconsistent. Example of a consistent non-coprime system: x ≡ 1 (mod 4) and x ≡ 5 (mod 6). Here both reduce to 1 mod 2, so the system is consistent and the solution is unique mod lcm(4, 6) = 12 — namely x ≡ 5 (mod 12).

CRT vs alternative methods for solving congruences

Method	Best for	Complexity	Limitation	Output
Direct enumeration	Small M ≤ 1000	O(M)	Exponential in bitsize	Solution mod M
CRT (constructive)	Pairwise coprime moduli	O(k log² M)	Requires coprimality	Solution mod M
Iterative pairing	Arbitrary moduli	O(k log² M)	Solvability check needed	Solution mod lcm(m_i)
Garner's algorithm	RSA-style implementation	O(k²) for k moduli	Pairwise coprime only	Mixed-radix representation
Lagrange interpolation	Polynomial residues	O(k²)	Polynomial setting	Polynomial mod ∏(x−r_i)
Hensel lifting	Refining mod p^k	O(log k) iterations	One prime base	Lifts mod p to mod p^k
Brute search	Small composite k=2 only	O(min(m_i))	Exponential at scale	Direct test

For RSA-scale moduli (1024-bit primes), the constructive CRT formula plus extended Euclidean gives the answer in milliseconds; direct enumeration over the product M ≈ 2^2048 is hopeless. CRT's value is precisely the conversion from "exponential in bit-size" to "polynomial in bit-size."

Where the Chinese Remainder Theorem shows up

• RSA decryption — CRT-RSA speedup. Given private key (d, p, q) with n = pq, decryption m = c^d mod n is rewritten as m_p = c^(d mod (p−1)) mod p and m_q = c^(d mod (q−1)) mod q, then recombined via CRT. Modular exponentiation is roughly cubic in modulus size, so two 1024-bit exponentiations replace one 2048-bit exponentiation, yielding ~4× speedup. OpenSSL's RSA_private_decrypt uses CRT-RSA by default and stores p, q, dP, dQ, qInv in the private key file.
• Residue number systems in DSP. Hardware FFT and convolution units split a wide-precision integer into residues modulo small primes (e.g. 2^31 − 1, 2^31 − 5, 2^29 − 3), do all operations componentwise in parallel, then reconstruct via CRT. NVIDIA's GPU Number-Theoretic Transform implementations and lattice-cryptography hardware (Kyber, Dilithium) are built on RNS arithmetic.
• Sun Zi's puzzle and recreational mathematics. The original 4th-century AD problem ("counting in threes leaves 2, in fives leaves 3, in sevens leaves 2") set the template for centuries of number-theoretic puzzles. The Korean astronomer Hong Jeong-ha (1717) used CRT-style techniques to align lunar and solar calendars.
• Computer algebra systems — modular reconstruction. SageMath, Mathematica and Maple compute large polynomial and integer determinants by reducing modulo many small primes, computing each in parallel, and reconstructing via CRT. Bareiss-style algorithms with rational reconstruction are 100× faster than direct Gaussian elimination on large symbolic matrices.
• Distributed counting and Bloom-filter unions. When several servers each count events with different moduli (one server tracks mod 31, another mod 37), CRT recovers the true count assuming it is below the product. The technique appears in approximate-counting structures and in distributed hash tables that combine partial enumerations.

Variants and extensions

• Garner's algorithm. A specific implementation of CRT optimised for software: instead of computing x directly, store x in a "mixed-radix" form that delays the final modular reduction until the answer is needed. Used in textbook RSA implementations to minimise large-integer multiplications.
• CRT for polynomial rings. If f(x) and g(x) are coprime polynomials, then ℝ[x] / (f·g) ≅ ℝ[x]/f × ℝ[x]/g. Used in error-correcting codes (Reed–Solomon decoding) and in the proof of Lagrange interpolation as a special case.
• Generalised CRT for ideals. In any commutative ring, if I_1, ..., I_k are pairwise coprime ideals (I_i + I_j = R for i ≠ j), then R / (I_1 · I_2 · ... · I_k) ≅ R/I_1 × ... × R/I_k. The integer case is the prototype, but the abstract version covers any ring.
• Hensel lifting. Given a solution mod p, repeatedly lift to mod p², p⁴, p⁸, ... A close cousin to CRT — both reconstruct global information from local pieces, but Hensel works one prime power at a time while CRT combines many primes.
• CRT for primality testing. The Lenstra–Pomerance–Wagstaff primality test uses CRT-style lifting to verify that a candidate prime n satisfies a^n ≡ a (mod n) over multiple bases simultaneously, with the moduli combined for efficiency.

Common pitfalls

• Forgetting to verify pairwise coprimality. The constructive formula breaks if any two m_i share a factor. Always verify gcd(m_i, m_j) = 1 for all pairs before applying the standard recipe.
• Computing modular inverses incorrectly. y_i = M_i^(−1) mod m_i requires the extended Euclidean algorithm, not just Fermat's little theorem (which only works when m_i is prime). For composite m_i, use the EEA: gcd(M_i, m_i) = 1 implies there are integers s, t with s · M_i + t · m_i = 1, so y_i = s mod m_i.
• Assuming the unique solution is positive or in [0, M). The CRT formula often produces a representative outside the canonical range. Reduce mod M at the end, choosing the representative in [0, M) or (−M/2, M/2] depending on convention.
• Wrong answer when moduli aren't coprime. If gcd(m_i, m_j) > 1, you must use the generalised CRT and verify a_i ≡ a_j (mod gcd(m_i, m_j)). Using the standard formula with non-coprime moduli silently produces nonsense.
• Ignoring the cost of large-integer arithmetic. The "k modular inverses and k multiplications" recipe is O(k) operations, but each operation on the product M can be O(k²) bits. The total complexity is dominated by the large multiplications, not the number of moduli.