Lesson 6 of 8 · Number Theory
The Chinese Remainder Theorem
A system of "n leaves remainder r₁ mod m₁, and remainder r₂ mod m₂, ..." always has a solution when the moduli are pairwise coprime — and finding it is just a sequence of small searches, not an intimidating theorem to memorize. When the moduli aren't coprime, one extra compatibility check tells you whether a solution exists at all.
Mark your status for this lesson:
Learning objectives
- Solve a system of two or three simultaneous congruences by successive substitution.
- Combine congruences step by step: solve the first pair, then bring in each additional congruence.
- Check compatibility when moduli share a common factor, and recognize when no solution exists.
- Recognize the "all remainders equal" shortcut that reduces a CRT system to a pure lcm question.
The core idea
The Chinese Remainder Theorem guarantees that a system of congruences with pairwise coprime moduli has exactly one solution modulo the product of the moduli. In practice, you rarely need the theorem's formal machinery — you solve the system directly, one congruence at a time: list numbers satisfying the first congruence, then check them against the second, and so on.
When moduli share a common factor, a solution isn't guaranteed. The two congruences must agree on that shared factor — if a ≡ r₁ (mod m₁) and a ≡ r₂ (mod m₂) with g = gcd(m₁,m₂), a solution exists exactly when r₁ ≡ r₂ (mod g).
The theorem (coprime case)
If m₁, m₂, ..., mₖ are pairwise coprime, the system n ≡ rᵢ (mod mᵢ) for each i has exactly one solution modulo m₁m₂⋯mₖ.
Successive substitution (the practical method)
List the numbers satisfying the first congruence (r, r+m₁, r+2m₁, ...), and check each against the second congruence. Once found, that combined congruence (mod lcm of the two moduli) becomes the new "first" congruence, and you bring in the next one.
Compatibility for non-coprime moduli
solvable ⟺ r₁ ≡ r₂ (mod gcd(m₁,m₂))
Always check this first when moduli share a factor — if it fails, no search will ever find a solution.
Worked example 1 — Two congruences, coprime moduli
Problem
Find the smallest positive integer n with n ≡ 3 (mod 4) and n ≡ 2 (mod 9).
Key insight
List numbers satisfying the first congruence, and check each against the second.
Solution
3, 7, 11, ... — checking mod 9: 11 mod 9 = 2. n = 11.
Takeaway
Since gcd(4,9)=1, a solution is guaranteed — the only work is the short search.
Worked example 2 — Three congruences
Problem
Find the smallest positive integer n with n ≡ 1 (mod 3), n ≡ 2 (mod 5), and n ≡ 3 (mod 7).
Key insight
Combine two congruences at a time — solve the first pair, then bring the third congruence into the combined result.
Solution
First pair: checking 1, 4, 7, 10, 13, ... against mod 5 — 7 mod 5 = 2, so n ≡ 7 (mod 15). Now bring in mod 7: 7, 22, 37, ... — 52 mod 7 = 3. n = 52.
Takeaway
Each additional congruence is handled the same way — combine two at a time, never all at once.
Worked example 3 — Non-coprime moduli
Problem
Does there exist an integer n with n ≡ 1 (mod 6) and n ≡ 3 (mod 8)?
Key insight
gcd(6,8) = 2. Check whether the two remainders agree mod 2 before searching.
Solution
1 mod 2 = 1, but 3 mod 2 = 1 — they agree! So a solution does exist. (Searching confirms n = 19.)
Takeaway
Agreement on the shared factor doesn't guarantee the two original moduli are coprime — it just guarantees a solution exists, found the same way as always.
Worked example 4 — The "equal remainders" shortcut
Problem
Find the smallest integer n > 1 with n ≡ 1 (mod 3), n ≡ 1 (mod 4), and n ≡ 1 (mod 5).
Key insight
Every remainder is 1, so n − 1 must be divisible by 3, 4, and 5 simultaneously — that's just an lcm question.
Solution
n − 1 = lcm(3,4,5) = 60. n = 61.
Takeaway
Always check whether all the remainders are equal before doing a full successive-substitution search — it's a dramatic shortcut when it applies.
Strategy notes
Solve two congruences at a time, never all at once
Combine the first two into a single congruence mod their lcm, then treat that as the new "first" congruence when bringing in the next one. This keeps every step a short, manageable search.
Check for the "equal remainders" shortcut first
If every congruence in the system has the same remainder r, the problem reduces immediately to n − r being divisible by the lcm of all the moduli — much faster than the general method.
Common mistakes
Assuming a solution always exists
The guarantee only holds for pairwise coprime moduli. When moduli share a factor, always check compatibility mod that shared factor first.
Searching against the wrong modulus after combining
Once two congruences are combined into "n ≡ r (mod lcm)", the next search must be against that combined lcm, not against either original modulus individually.
Reporting a solution beyond the smallest positive one
A CRT system's solutions repeat with period equal to the lcm of all moduli — always report the smallest positive value unless the problem specifically asks for something else.
Practice
20 questions across four difficulty tiers. Most want a single number (the smallest positive integer satisfying the system). One question asks whether a solution exists at all — answer yes or no. Up to three tries per question before the solution is shown.