1
Coprimality is the hypothesis
Without it the system may be inconsistent (x ≡ 1 mod 4 and x ≡ 2 mod 6) or have several solutions.
Lesson · Number Theory and Cryptography · Congruences
The Chinese Remainder Theorem
Given remainders modulo pairwise coprime numbers, there is exactly one integer modulo their product with those remainders. It is constructive, and it is why RSA implementations run about four times faster than the naive method.
x ≡ a₁ (mod m₁), …, x ≡ a_k (mod m_k) with mᵢ PAIRWISE COPRIME
⟹ a unique solution modulo M = m₁⋯m_k
x = Σ aᵢ Mᵢ yᵢ where Mᵢ = M/mᵢ and yᵢ = Mᵢ⁻¹ mod mᵢ
coprimality is essential
Existence and uniqueness
Core ideas
What this lesson establishes
A number is determined by its remainders, provided the moduli share no factors.
2
The construction is explicit
Each term contributes the right remainder to its own modulus and 0 to the others, so the sum has all the required remainders at once.
3
It splits a big modulus into small ones
Working modulo pq is equivalent to working modulo p and modulo q separately, which is a real speed-up when p and q are large.
The material
The theorem
Statement, construction, proof, and the application to RSA.
Theorem · Chinese remainder theorem
Let m₁, …, m_k be pairwise coprime positive integers and M = m₁⋯m_k. For any a₁, …, a_k the system x ≡ aᵢ (mod mᵢ) has exactly one solution modulo M.
Construction. Let Mᵢ = M/mᵢ. Since the moduli are pairwise coprime, gcd(Mᵢ, mᵢ) = 1, so Mᵢ has an inverse yᵢ modulo mᵢ. Set x = Σ aᵢ Mᵢ yᵢ.
Modulo mⱼ, every term with i ≠ j vanishes because mⱼ | Mᵢ. The remaining term is aⱼ Mⱼ yⱼ ≡ aⱼ · 1 = aⱼ. So x satisfies every congruence.
Uniqueness. If x and x' both solve the system, then mᵢ | (x − x') for every i. Pairwise coprimality gives M | (x − x'), so x ≡ x' (mod M).
□
The construction is the theorem's real content. Each term is built to be invisible to every modulus but its own, so the terms do not interfere and the sum can satisfy all the congruences simultaneously.
Example · Sun Tzu's problem
"There are things whose number is unknown. Divided by 3 the remainder is 2; by 5 the remainder is 3; by 7 the remainder is 2." With M = 105: M₁ = 35, y₁ = 2; M₂ = 21, y₂ = 1; M₃ = 15, y₃ = 1. So x = 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105). Check: 23 = 7·3 + 2, 23 = 4·5 + 3, 23 = 3·7 + 2. The problem is from a Chinese text of the third century.
Coprimality is not optional
Example · Inconsistent
x ≡ 1 (mod 4) and x ≡ 2 (mod 6) has no solution: the first makes x odd and the second makes it even. gcd(4,6) = 2 and the remainders disagree modulo 2.
Example · Consistent but not unique modulo the product
x ≡ 1 (mod 4) and x ≡ 3 (mod 6) has solutions x ≡ 9 (mod 12), not modulo 24. The correct modulus for non-coprime systems is the lcm, and consistency requires the remainders to agree modulo every pairwise gcd.
Why RSA implementations use it
Decryption computes c^d mod n with n = pq. By the theorem, that is equivalent to computing c^d mod p and c^d mod q and recombining. The two exponentiations use numbers half the size, and modular multiplication costs roughly the square of the operand size — so each is about four times cheaper, and two of them together about twice.
In practice the exponents can also be reduced modulo p − 1 and q − 1 by Fermat's theorem (“Fermat's Little Theorem and Euler's Theorem”), which is where the rest of the speed-up comes from. The overall gain is roughly a factor of four, and essentially every RSA implementation does this.
Interactive
Number theory workbench
Algorithms with their traces
Method
Solving a system
Check coprimality, then build the solution term by term.
1
Check the moduli are pairwise coprime
If not, the system may be inconsistent, and if consistent the modulus of the answer is the lcm rather than the product.
2
Compute M and each Mᵢ = M/mᵢ
Mᵢ is divisible by every modulus except the ith, which is what makes the terms independent.
3
Invert each Mᵢ modulo mᵢ
By the extended algorithm. These are the yᵢ.
4
Sum and reduce
x = Σ aᵢMᵢyᵢ (mod M), then verify every original congruence.
The Chinese remainder theorem
Score 0 / 0Choose the answer you can justify.
Three congruences
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
M = 3 · 5 · 7 = 105
i mᵢ aᵢ Mᵢ = M/mᵢ yᵢ = Mᵢ⁻¹ mod mᵢ term aᵢMᵢyᵢ
1 3 2 35 35 ≡ 2, 2⁻¹ ≡ 2 140
2 5 3 21 21 ≡ 1, 1⁻¹ ≡ 1 63
3 7 2 15 15 ≡ 1, 1⁻¹ ≡ 1 30
x = 140 + 63 + 30 = 233 ≡ 233 − 2·105 = 23 (mod 105)
CHECK 23 mod 3 = 2 ✓
23 mod 5 = 3 ✓
23 mod 7 = 2 ✓
Each Mᵢ was reduced modulo its own mᵢ before inverting, which keeps the numbers small: inverting 35 modulo 3 is inverting 2 modulo 3. The solution is unique modulo 105, so 23, 128, 233 and −82 are all the same answer.
Common mistakes
1
Applying it without checking coprimalityNon-coprime moduli may be inconsistent, and when they are consistent the answer is unique modulo the lcm, not the product.
2
Inverting Mᵢ modulo the wrong thingyᵢ is the inverse of Mᵢ modulo mᵢ, not modulo M. Reducing Mᵢ first makes the inversion small.
3
Forgetting to reduce the final sumThe construction gives a solution; the canonical answer lies in [0, M).
Check your understanding
✓
Finish when you can construct the solution rather than search for it.
Solve x ≡ 1 (mod 5), x ≡ 2 (mod 7), x ≡ 3 (mod 9) by the construction. Searching would take up to 315 trials; the construction takes three inversions.
Note: The theorem is an isomorphism: ℤ_{mn} ≅ ℤ_m × ℤ_n for coprime m, n, and it respects both addition and multiplication. That structural statement is why the RSA speed-up works — the arithmetic really does split.