Sunzi's problem: x≡2(mod3), x≡3(mod5), x≡2(mod7). Here N=105. Combine the first two: write x=3+5t; then 3+5t≡2(mod3) means 2t≡2, so t≡1 and x≡8(mod15). Next write x=8+15s: 8+15s≡2(mod7) means 1+s≡2, so s=1 and x=23. Check: 23mod3=2, 23mod5=3, 23mod7=2. So x≡23(mod105).
Two more: x≡1(mod4), x≡2(mod9) gives x≡29(mod36); x≡3(mod5), x≡4(mod7) gives x≡18(mod35). Each step solves a linear congruence (linear congruences) using inverses from Bézout's identity. The moduli must be coprime: if they share a factor the system may be inconsistent.
The theorem says that ZN is isomorphic to the product of the Zni, which is why φ(N)=∏φ(ni) (Euler's totient) and why cyclic groups of coprime orders combine (the fundamental theorem of finite abelian groups). It speeds up arithmetic in RSA (RSA) by working modulo p and q separately.
What is it used for?
The Chinese remainder theorem combines congruences with coprime moduli into one congruence modulo the product.
Solving systems of congruences.
Fast modular arithmetic.
RSA.
How to use chinese remainder theorem
Check that the moduli are pairwise coprime.
Write x=a1+n1t and substitute into the next congruence.
Solve for t, then combine moduli.
Repeat and check each congruence.
Graph
The solution is unique modulo 105.
Worked examples
These examples are worked by hand, step by step, so you can compare your own working.
Example 1: Sunzi's problem
Solve x≡2(3), x≡3(5), x≡2(7).
Worked example
Answer
23
Combine mod 3 and 5
x≡8(mod15)
Combine with mod 7
x≡23(mod105)
Example 2: moduli 4 and 9
Solve x≡1(4), x≡2(9).
Worked exampleAnswer checked
Answer
29(mod36)
Check
29=7⋅4+1=3⋅9+2
Example 3: moduli 5 and 7
Solve x≡3(5), x≡4(7).
Worked exampleAnswer checked
Answer
18(mod35)
Check
18=3⋅5+3=2⋅7+4
Special cases
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
x ≡ 2 (3), x ≡ 3 (5)
x ≡ 8 (mod 15)
8 mod 3 = 2, 8 mod 5 = 3.
x ≡ 1 (4), x ≡ 2 (9)
x ≡ 29 (mod 36)
Check.
Three congruences
x ≡ 23 (mod 105)
2 (3), 3 (5), 2 (7).
Modulus
3 × 5 × 7
105.
Word problems
If the moduli m₁, …, m_k are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = ∏mᵢ.
Two moduli
Check x = 8 against x ≡ 2 (mod 3).
8 mod 3
Check: 2 ✓2
Second condition
Check x = 8 against x ≡ 3 (mod 5).
8 mod 5
Check: 3 ✓3
Different moduli Higher
Check x = 29 modulo 9 (needs 2).
29 mod 9
Check: 2 ✓2
Three moduli Higher
Find the combined modulus for 3, 5, 7.
3 × 5 × 7
Check: ✓105
Common mistakes
Non-coprime moduli
always solvable ✗
need pairwise coprime ✓
e.g. 4 and 6.
Modulus sum
3 + 5 ✗
3 × 5 ✓
Product.
Unique integer
one integer ✗
one residue class ✓
Add multiples of M.
Skipping verification
unchecked ✗
check each congruence ✓
Always check.
Exam tips
Pairwise coprime moduli.
M = ∏mᵢ.
Check each congruence.
Unique mod M.
Inverses build the solution.
Practice questions
Try each one on paper, then open the answer. Use the solver above to see the full working.
1. 8 mod 5 Foundation
3
2. 23 mod 3 Foundation
2
3. 29 mod 4 Foundation
1
4. Modulus for 4, 9, 5 Higher
180
5. Smallest x with x≡1 (2), x≡2 (3) Higher
5
6. 23 mod 5 Higher
3
Practice generator
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
Key terms
Chinese remainder theorem
Solves simultaneous congruences.
Pairwise coprime
Every pair has gcd 1.
Combined modulus (M)
Product.
Residue class
All solutions mod M.
Modular inverse
Used in the construction.
Simultaneous congruence
System of congruences.
Frequently asked questions
What does the CRT say?
Coprime moduli give a unique solution modulo their product.