18.10 Chinese Remainder Theorem
The Chinese Remainder Theorem is a reconstruction tool.
18.10 Chinese Remainder Theorem
The Chinese Remainder Theorem is a reconstruction tool. It lets you replace one computation modulo a large number with several computations modulo smaller numbers, then combine the answers into a unique result modulo the product of those smaller moduli.
This pattern appears in number theory, cryptography, high-performance arithmetic, coding theory, calendar calculations, and algorithmic problem solving. It is especially useful when the smaller moduli are pairwise coprime, because each congruence contributes independent information.
Problem
Given a system of congruences:
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)
find an integer x satisfying all congruences.
When the moduli are pairwise coprime, the solution is unique modulo:
M = m₁ × m₂ × ... × mₖ
Example:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
One solution is:
x = 23
Check:
23 mod 3 = 2
23 mod 5 = 3
23 mod 7 = 2
All other solutions are congruent to 23 modulo:
3 × 5 × 7 = 105
So the solution class is:
x ≡ 23 (mod 105)
Pairwise Coprime Moduli
The simplest form of the theorem requires:
gcd(mᵢ, mⱼ) = 1
for every pair of distinct moduli.
For example:
3, 5, 7
are pairwise coprime.
But:
6, 10, 15
are not pairwise coprime, because:
gcd(6,10) = 2
gcd(6,15) = 3
gcd(10,15) = 5
The pairwise-coprime condition guarantees that every residue system has exactly one solution modulo the product.
Constructive Formula
Let:
M = m₁m₂...mₖ
For each modulus mᵢ, define:
Mᵢ = M / mᵢ
Since mᵢ is coprime to Mᵢ, there exists an inverse:
yᵢ = Mᵢ⁻¹ mod mᵢ
Then:
x = Σ aᵢ Mᵢ yᵢ
modulo M.
This formula works because each term is designed to affect exactly one congruence and vanish under all the others.
Example
Solve:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
First compute:
M = 3 × 5 × 7 = 105
For modulus 3:
M₁ = 105 / 3 = 35
We need:
35y₁ ≡ 1 (mod 3)
Since:
35 ≡ 2 (mod 3)
and:
2 × 2 ≡ 1 (mod 3)
we have:
y₁ = 2
For modulus 5:
M₂ = 105 / 5 = 21
Need:
21y₂ ≡ 1 (mod 5)
Since:
21 ≡ 1 (mod 5)
we have:
y₂ = 1
For modulus 7:
M₃ = 105 / 7 = 15
Need:
15y₃ ≡ 1 (mod 7)
Since:
15 ≡ 1 (mod 7)
we have:
y₃ = 1
Now combine:
x =
2 × 35 × 2
+ 3 × 21 × 1
+ 2 × 15 × 1
x = 140 + 63 + 30 = 233
Reduce modulo 105:
233 mod 105 = 23
Therefore:
x ≡ 23 (mod 105)
Why the Formula Works
Consider one term:
aᵢ Mᵢ yᵢ
Modulo mᵢ, we have:
Mᵢ yᵢ ≡ 1
so the term becomes:
aᵢ
Modulo any other mⱼ, the product Mᵢ contains mⱼ, so:
Mᵢ ≡ 0 (mod mⱼ)
Thus the term contributes zero to all other congruences.
The sum therefore satisfies each congruence independently.
Implementation
We need modular inverses. Use the Extended Euclidean Algorithm.
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return g, x, y
def mod_inverse(a, m):
g, x, _ = extended_gcd(a, m)
if g != 1:
raise ValueError("inverse does not exist")
return x % m
Now implement CRT for pairwise-coprime moduli.
def crt(remainders, moduli):
if len(remainders) != len(moduli):
raise ValueError("remainders and moduli must have same length")
M = 1
for m in moduli:
M *= m
x = 0
for a_i, m_i in zip(remainders, moduli):
M_i = M // m_i
y_i = mod_inverse(M_i, m_i)
x += a_i * M_i * y_i
return x % M, M
Example:
remainders = [2, 3, 2]
moduli = [3, 5, 7]
print(crt(remainders, moduli))
Output:
(23, 105)
The pair (23, 105) means:
x ≡ 23 (mod 105)
Incremental CRT
The constructive formula is clean, but an incremental method is often easier to adapt.
Suppose we already have:
x ≡ r (mod m)
and we want to merge:
x ≡ a (mod n)
For coprime m and n, write:
x = r + mt
Substitute into the second congruence:
r + mt ≡ a (mod n)
Then:
mt ≡ a - r (mod n)
Since m has an inverse modulo n:
t ≡ (a-r)m⁻¹ (mod n)
This gives the merged solution modulo:
mn
Implementation:
def crt_incremental(remainders, moduli):
r = 0
m = 1
for a, n in zip(remainders, moduli):
inv = mod_inverse(m, n)
t = ((a - r) * inv) % n
r = r + m * t
m = m * n
r %= m
return r, m
This version is useful when congruences arrive one at a time.
Non-Coprime Moduli
The general CRT can also handle moduli that are not coprime.
Two congruences:
x ≡ a (mod m)
x ≡ b (mod n)
are compatible if and only if:
a ≡ b (mod gcd(m,n))
Equivalently:
gcd(m,n) | (b-a)
Example with a solution:
x ≡ 2 (mod 6)
x ≡ 8 (mod 10)
Here:
gcd(6,10) = 2
and:
8 - 2 = 6
which is divisible by 2.
So a solution exists.
Example with no solution:
x ≡ 1 (mod 6)
x ≡ 4 (mod 10)
Here:
gcd(6,10) = 2
but:
4 - 1 = 3
is not divisible by 2.
No integer can satisfy both congruences.
General Merge Formula
To merge:
x ≡ r (mod m)
x ≡ a (mod n)
write:
x = r + mt
Then:
mt ≡ a-r (mod n)
Let:
g = gcd(m,n)
A solution exists only if:
(a-r) % g == 0
Divide by g:
(m/g)t ≡ (a-r)/g (mod n/g)
Now m/g and n/g are coprime, so an inverse exists.
from math import gcd
def crt_general_pair(r, m, a, n):
g = gcd(m, n)
if (a - r) % g != 0:
return None
m_div = m // g
n_div = n // g
diff = (a - r) // g
t = (diff * mod_inverse(m_div, n_div)) % n_div
lcm = m * n_div
result = (r + m * t) % lcm
return result, lcm
Merging a full list:
def crt_general(remainders, moduli):
r = 0
m = 1
for a, n in zip(remainders, moduli):
merged = crt_general_pair(r, m, a, n)
if merged is None:
return None
r, m = merged
return r, m
Application: Reconstructing Large Computations
Suppose a computation modulo a large composite number is expensive or inconvenient. If the modulus factors into coprime parts, we can compute separately under each modulus and reconstruct.
Example:
M = 1000000007 × 1000000009
Instead of computing directly modulo M, compute:
x mod 1000000007
x mod 1000000009
Then reconstruct using CRT.
This is useful when intermediate values would otherwise exceed a machine word or when a library provides optimized arithmetic for smaller moduli.
Application: RSA Optimization
RSA private-key operations can be accelerated using CRT.
Instead of computing:
m = c^d mod n
where:
n = pq
compute separately:
m₁ = c^d mod p
m₂ = c^d mod q
Then combine the results using CRT.
This is substantially faster because exponentiation modulo smaller primes is cheaper than exponentiation modulo n.
Application: Calendar and Scheduling Problems
CRT also appears in cyclic scheduling.
Example:
x ≡ 1 (mod 7)
x ≡ 3 (mod 11)
This can represent an event that must occur one day after a weekly cycle begins and three days after an eleven-day maintenance cycle begins.
CRT finds the first time both conditions are satisfied.
Common Mistakes
Forgetting Pairwise Coprimality
The simple formula assumes pairwise-coprime moduli. If moduli are not coprime, use the general merge method.
Failing to Check Compatibility
For non-coprime moduli, not every system has a solution.
Always check:
gcd(m,n) | (a-r)
Returning One Integer Without the Modulus
CRT returns a residue class, not just a value.
Return both:
(result, modulus)
Overflow in the Product
The product:
M = m₁m₂...mₖ
can exceed fixed-width integer limits. Use big integers or incremental merging if needed.
Negative Remainders
Normalize remainders into the range:
0 ≤ aᵢ < mᵢ
before merging.
Testing
Basic tests:
def test_crt():
x, m = crt([2, 3, 2], [3, 5, 7])
assert m == 105
assert x == 23
assert x % 3 == 2
assert x % 5 == 3
assert x % 7 == 2
General CRT tests:
def test_crt_general():
assert crt_general([2, 8], [6, 10]) == (8, 30)
assert crt_general([1, 4], [6, 10]) is None
The first case has solutions:
8, 38, 68, ...
all congruent modulo 30.
Takeaway
The Chinese Remainder Theorem combines multiple modular constraints into a single congruence. With pairwise-coprime moduli, the solution is unique modulo the product and can be constructed using modular inverses. The general version also handles non-coprime moduli, provided the congruences are compatible. CRT is a standard tool for modular reconstruction, cryptographic acceleration, cyclic scheduling, high-performance arithmetic, and many number-theoretic algorithms.