Back
LEVEL 4
Chinese Remainder Theorem
How It Works
What is Modulo?
"x ≡ 2 (mod 3)" means x leaves remainder 2 when divided by 3. So x could be: 2, 5, 8, 11, 14 ... (add 3 each time)
Two Conditions
CRT finds a number x that satisfies TWO remainder conditions simultaneously. Both must be true at once.
List & Check
List numbers satisfying condition 1: e.g. x≡2(mod3) → 2,5,8,11... Now check each against condition 2.
Pattern Repeats
Solutions repeat every (mod1 × mod2) numbers. So once you find one answer, the next is answer + (mod1×mod2).
Ancient Puzzle: Eggs in a Basket
"A merchant has eggs. Groups of 3 leave 2. Groups of 5 leave 3. Smallest number?"
Condition 1: x ≡ 2 (mod 3) → 2, 5, 8, 11, 14...
Condition 2: x ≡ 3 (mod 5) → 3, 8, 13, 18...
Check 8: 8÷3 = 2 R 2 ✓ | 8÷5 = 1 R 3 ✓
Answer: 8 eggs!
Next solution: 8 + (3×5) = 23, then 38, then 53...
Real World Uses
1RSA encryption (internet security) uses CRT to speed up calculations by 4×.
2Computer clocks use CRT to synchronize across different frequency oscillators.
3The theorem is named after Sun Tzu (3rd century AD) — a different Sun Tzu than Art of War!