What does the Chinese Remainder Theorem say?
Suppose you know the remainders of an unknown integer x when divided by several pairwise coprime moduli, for example x leaves remainder 2 when divided by 3, remainder 3 when divided by 5 and remainder 2 when divided by 7. The Chinese Remainder Theorem (CRT) says there is exactly one solution modulo the product of the moduli, here 3 × 5 × 7 = 105, and in this case it is x ≡ 23 (mod 105).
The theorem is named after problems in the Chinese text Sunzi Suanjing from roughly the third to fifth century. Today it is used to speed up RSA decryption, to split large computations into small ones, and to reconstruct numbers from residues in computer algebra.
How the calculator solves the system
The calculator merges the congruences one at a time. Given x ≡ x₀ (mod M) and a new equation x ≡ a (mod m), it writes x = x₀ + M·k and solves M·k ≡ a − x₀ (mod m) for k with the extended Euclidean algorithm. The result is a single congruence modulo lcm(M, m), and the process repeats until only one remains. Every merge is displayed with the numbers substituted so you can reproduce it.
This approach also handles moduli that share factors. Then a solution exists only if a − x₀ is divisible by gcd(M, m), and the combined modulus is the least common multiple rather than the product. For instance x ≡ 1 (mod 4) and x ≡ 3 (mod 6) is solvable (x = 9, unique modulo lcm = 12), because 3 − 1 = 2 is divisible by gcd(4, 6) = 2, whereas x ≡ 1 (mod 4) and x ≡ 2 (mod 6) has no solution because 2 − 1 = 1 is not divisible by 2.
The classical formula
For pairwise coprime moduli m₁…mₖ with product M, let Mᵢ = M / mᵢ and let yᵢ be the inverse of Mᵢ modulo mᵢ. Then x = Σ aᵢ·Mᵢ·yᵢ (mod M). The merging method used here gives the same answer and extends naturally to non-coprime moduli.
Reading the answer
The answer is reported as the smallest non-negative solution together with the modulus M, so every solution is x = x₀ + M·t. If the system has no solution, the calculator tells you which pair of congruences conflicts and why. Negative residues are accepted and reduced into the range 0 to m − 1 before solving.
Worked examples
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
Sunzi: 2 mod 3, 3 mod 5, 2 mod 7
- Congruences x ≡ a (mod m):
(2, 3); (3, 5); (2, 7)
Smallest non-negative solution
23
x ≡ 23 (mod 105)
The moduli are pairwise coprime, so the solution is unique modulo M = 105 (the product of the moduli).
Step-by-step solution
Formula used
x ≡ aᵢ (mod mᵢ), i = 1…k; M = lcm(m₁, …, mₖ)
Pairwise coprime case: x = Σ aᵢ·Mᵢ·(Mᵢ⁻¹ mod mᵢ) mod M, with Mᵢ = M / mᵢ
NoteThe system
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
NoteAre the moduli pairwise coprime?
Yes, so the Chinese Remainder Theorem guarantees exactly one solution modulo the product of the moduli.
CalculateMerge with equation 2
x = x₀ + M·k with M·k ≡ a − x₀ (mod m)
We have x ≡ 2 (mod 3) and want x ≡ 3 (mod 5).
Write x = 2 + 3·k. Then 3·k ≡ 1 (mod 5).
gcd(3, 5) = 1 (coprime, so the inverse of 3 mod 5 exists)
k ≡ 2 (mod 5)
x = 2 + 3 × 2 = 8 ≡ 8 (mod 15)
CalculateMerge with equation 3
x = x₀ + M·k with M·k ≡ a − x₀ (mod m)
We have x ≡ 8 (mod 15) and want x ≡ 2 (mod 7).
Write x = 8 + 15·k. Then 15·k ≡ -6 (mod 7).
gcd(15, 7) = 1 (coprime, so the inverse of 1 mod 7 exists)
k ≡ 1 (mod 7)
x = 8 + 15 × 1 = 23 ≡ 23 (mod 105)
ResultSolution
x ≡ 23 (mod 105)
All solutions: x = 23 + 105·t for any integer t.
CheckVerify every congruence
23 mod 3 = 2 ✓
23 mod 5 = 3 ✓
23 mod 7 = 2 ✓
Non-coprime: 2 mod 6, 8 mod 10
- Congruences x ≡ a (mod m):
(2, 6); (8, 10)
Smallest non-negative solution
8
x ≡ 8 (mod 30)
The moduli share factors, but the system is consistent; the solution is unique modulo the least common multiple 30.
Step-by-step solution
Formula used
x ≡ aᵢ (mod mᵢ), i = 1…k; M = lcm(m₁, …, mₖ)
Pairwise coprime case: x = Σ aᵢ·Mᵢ·(Mᵢ⁻¹ mod mᵢ) mod M, with Mᵢ = M / mᵢ
NoteThe system
x ≡ 2 (mod 6)
x ≡ 8 (mod 10)
NoteAre the moduli pairwise coprime?
No. A solution exists only if every pair of congruences agrees modulo the gcd of their moduli; the steps below check this as they combine the equations.
CalculateMerge with equation 2
x = x₀ + M·k with M·k ≡ a − x₀ (mod m)
We have x ≡ 2 (mod 6) and want x ≡ 8 (mod 10).
Write x = 2 + 6·k. Then 6·k ≡ 6 (mod 10).
gcd(6, 10) = 2 divides 6, so the equation can be divided through by it
k ≡ 1 (mod 5)
x = 2 + 6 × 1 = 8 ≡ 8 (mod 30)
ResultSolution
x ≡ 8 (mod 30)
All solutions: x = 8 + 30·t for any integer t.
CheckVerify every congruence
8 mod 6 = 2 ✓
8 mod 10 = 8 ✓
No solution: 1 mod 4, 2 mod 6
- Congruences x ≡ a (mod m):
(1, 4); (2, 6)
Solution
No solution
the congruences are inconsistent
No integer satisfies all the congruences at once.
Step-by-step solution
Formula used
x ≡ aᵢ (mod mᵢ) is solvable iff aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)) for all pairs
NoteThe system
x ≡ 1 (mod 4)
x ≡ 2 (mod 6)
NoteAre the moduli pairwise coprime?
No. A solution exists only if every pair of congruences agrees modulo the gcd of their moduli; the steps below check this as they combine the equations.
CalculateCombine the equations one by one
Current solution before row 2: x ≡ 1 (mod 4)
Next congruence: x ≡ 2 (mod 6)
ResultInconsistent system
gcd(4, 6) = 2
2 − 1 = 1 is not divisible by 2, so the two congruences contradict each other.
Four equations
- Congruences x ≡ a (mod m):
(1, 2); (2, 3); (3, 5); (4, 7)
Smallest non-negative solution
53
x ≡ 53 (mod 210)
The moduli are pairwise coprime, so the solution is unique modulo M = 210 (the product of the moduli).
Step-by-step solution
Formula used
x ≡ aᵢ (mod mᵢ), i = 1…k; M = lcm(m₁, …, mₖ)
Pairwise coprime case: x = Σ aᵢ·Mᵢ·(Mᵢ⁻¹ mod mᵢ) mod M, with Mᵢ = M / mᵢ
NoteThe system
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 4 (mod 7)
NoteAre the moduli pairwise coprime?
Yes, so the Chinese Remainder Theorem guarantees exactly one solution modulo the product of the moduli.
CalculateMerge with equation 2
x = x₀ + M·k with M·k ≡ a − x₀ (mod m)
We have x ≡ 1 (mod 2) and want x ≡ 2 (mod 3).
Write x = 1 + 2·k. Then 2·k ≡ 1 (mod 3).
gcd(2, 3) = 1 (coprime, so the inverse of 2 mod 3 exists)
k ≡ 2 (mod 3)
x = 1 + 2 × 2 = 5 ≡ 5 (mod 6)
CalculateMerge with equation 3
x = x₀ + M·k with M·k ≡ a − x₀ (mod m)
We have x ≡ 5 (mod 6) and want x ≡ 3 (mod 5).
Write x = 5 + 6·k. Then 6·k ≡ -2 (mod 5).
gcd(6, 5) = 1 (coprime, so the inverse of 1 mod 5 exists)
k ≡ 3 (mod 5)
x = 5 + 6 × 3 = 23 ≡ 23 (mod 30)
CalculateMerge with equation 4
x = x₀ + M·k with M·k ≡ a − x₀ (mod m)
We have x ≡ 23 (mod 30) and want x ≡ 4 (mod 7).
Write x = 23 + 30·k. Then 30·k ≡ -19 (mod 7).
gcd(30, 7) = 1 (coprime, so the inverse of 2 mod 7 exists)
k ≡ 1 (mod 7)
x = 23 + 30 × 1 = 53 ≡ 53 (mod 210)
ResultSolution
x ≡ 53 (mod 210)
All solutions: x = 53 + 210·t for any integer t.
CheckVerify every congruence
53 mod 2 = 1 ✓
53 mod 3 = 2 ✓
53 mod 5 = 3 ✓
53 mod 7 = 4 ✓
Frequently asked questions
Do the moduli have to be coprime?
No. If they are pairwise coprime a solution always exists and is unique modulo the product. If not, a solution exists only when every pair of equations agrees modulo the gcd of its moduli, and then it is unique modulo the lcm.
What is the classic example?
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) has the solution x ≡ 23 (mod 105). It comes from the Sunzi Suanjing.
Why can a system have no solution?
If two moduli share a factor g, both equations determine x modulo g, and those two remainders must be equal. For example x ≡ 1 (mod 4) and x ≡ 2 (mod 6) force x to be both odd and even.
How is CRT used in RSA?
Decryption computes the power modulo p and modulo q separately, which is about four times faster than working modulo n = pq, and then recombines the two results with the CRT.