Number Theory · Intermediate · 9 min read
The Chinese Remainder Theorem Explained with Examples
If you know the remainders of an unknown number when divided by several pairwise coprime moduli, the Chinese Remainder Theorem (CRT) pins the number down completely. This guide shows the step-by-step merging method, which also works when the moduli are not coprime.
The statement
Let m₁, …, mk be pairwise coprime and let M be their product. For any remainders a₁, …, ak, the system x ≡ aᵢ (mod mᵢ) has exactly one solution modulo M. In other words, residues modulo M correspond one-to-one to tuples of residues modulo the individual moduli.
Solving by merging
Take two congruences at a time. Write the solution of the first as x = a₁ + m₁k and substitute it into the second, which gives m₁k ≡ a₂ − a₁ (mod m₂). Solve for k using the inverse of m₁ modulo m₂. The pair collapses into one congruence modulo m₁m₂, and you continue with the next equation. This method is easy to carry out by hand and is the one used by the calculator.
When the moduli are not coprime
Let g = gcd(m₁, m₂). The two congruences are compatible exactly when g divides a₂ − a₁. If they are, the merged modulus is lcm(m₁, m₂) rather than the product. If g does not divide a₂ − a₁, there is no solution, because both equations constrain x modulo g and disagree.
Why it is useful
CRT lets you split one big computation into several small ones and recombine. RSA implementations use it to decrypt about four times faster, and it underlies residue number systems and secret sharing schemes.
Key formulas
x ≡ aᵢ (mod mᵢ), M = m₁m₂…mₖ (pairwise coprime)Merge: x = a₁ + m₁k with m₁k ≡ a₂ − a₁ (mod m₂)Compatible ⇔ gcd(m₁, m₂) | (a₂ − a₁); new modulus lcm(m₁, m₂)
Solved example
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
- Merge the first two: x = 2 + 3k and 2 + 3k ≡ 3 (mod 5), so 3k ≡ 1 (mod 5). The inverse of 3 modulo 5 is 2, so k ≡ 2 and x = 8. Hence x ≡ 8 (mod 15).
- Merge with the third: x = 8 + 15j and 8 + 15j ≡ 2 (mod 7). Since 15 ≡ 1 and 8 ≡ 1 (mod 7), this reads 1 + j ≡ 2, so j ≡ 1.
- Then x = 8 + 15 = 23, so x ≡ 23 (mod 105).
- Check: 23 = 7·3 + 2, 23 = 4·5 + 3 and 23 = 3·7 + 2.
Practice questions
Try each question first, then open the answer.
1. Solve x ≡ 1 (mod 3) and x ≡ 2 (mod 5).
x ≡ 7 (mod 15). Check: 7 = 2·3 + 1 and 7 = 1·5 + 2.
2. Does x ≡ 2 (mod 4) and x ≡ 3 (mod 6) have a solution?
No. gcd(4, 6) = 2 and 3 − 2 = 1 is not divisible by 2: the first forces x even, the second forces x odd.
3. Solve x ≡ 3 (mod 7) and x ≡ 4 (mod 9).
x ≡ 31 (mod 63). Check: 31 = 4·7 + 3 and 31 = 3·9 + 4.