The idea: remainders as coordinates
Divide a number x by 3 and by 5 and keep only the two remainders, x mod 3 and x mod 5. The Chinese Remainder Theorem (CRT) says that for x from 0 to 14 these two remainders are never the same pair twice. So the pair (x mod 3, x mod 5) names x exactly, as long as you only care about x mod 15. Draw a 3 × 5 grid with rows x mod 3 and columns x mod 5, and every number from 0 to 14 gets its own cell.
The diagonal walk
Adding 1 to x adds 1 to both remainders. In the grid, x + 1 sits one row down and one column right of x: the numbers walk diagonally. At the bottom edge the row wraps back to 0 (3 mod 3 = 0), and at the right edge the column wraps (5 mod 5 = 0). The walk comes back to cell (0, 0) only when x is a multiple of both 3 and 5, that is after lcm(3, 5) = 15 steps. Fifteen steps, fifteen cells, no cell twice: every cell is filled exactly once (Demo: walk 0..14 through the 3 × 5 grid).
The key fact is that 3 and 5 are coprime: gcd(3, 5) = 1, so their lcm is their product. The theorem in general: if m₁, …, mₖ are pairwise coprime and M = m₁·m₂·…·mₖ, then the system x ≡ aᵢ (mod mᵢ) has exactly one solution x in 0…M−1.
Solving by sieving
Take x ≡ 2 (mod 3) and x ≡ 3 (mod 5). The first congruence alone allows 2, 5, 8, 11, 14 (start at 2, add 3): that is row 2 of the grid. Test each one mod 5:
| x | x mod 5 | wanted 3? |
|---|---|---|
| 2 | 2 | ✗ |
| 5 | 0 | ✗ |
| 8 | 3 | ✓ |
| 11 | 1 | ✗ |
| 14 | 4 | ✗ |
Row 2 crosses every column once, so exactly one candidate passes: x = 8, and all solutions are 8 + 15k (Demo: sieve). Sieving is easy to do by hand but tries up to m₂ numbers; with moduli in the millions that is too slow.
Solving by construction
The construction builds the answer from pieces that each handle one congruence. Let M = 3 · 5 = 15 and, for each modulus, Mᵢ = M / mᵢ, the product of all the other moduli. Mᵢ is 0 modulo every other modulus. Then find yᵢ = Mᵢ⁻¹ mod mᵢ, the inverse, so that Mᵢ·yᵢ ≡ 1 (mod mᵢ). The term aᵢ·Mᵢ·yᵢ is then aᵢ modulo mᵢ and 0 modulo all the others, and the sum of the terms has every remainder right:
x = a₁·M₁·y₁ + a₂·M₂·y₂ (mod M)
M₁ = 15 / 3 = 5, 5·2 = 10 ≡ 1 (mod 3) → y₁ = 2, term₁ = 2·5·2 = 20
M₂ = 15 / 5 = 3, 3·2 = 6 ≡ 1 (mod 5) → y₂ = 2, term₂ = 3·3·2 = 18
x = 20 + 18 = 38 ≡ 8 (mod 15)
On the grid, term₁ fixes the row and stays in column 0, term₂ fixes the column and stays in row 0, and adding them combines both (Demo: construction with inverses). The inverses come from the extended Euclidean algorithm, shown on Euclidean Algorithm: GCD, Bézout and Modular Inverse; they exist exactly because each Mᵢ is coprime to mᵢ.
Three congruences: Sunzi's problem
The oldest known CRT problem is in the Sunzi Suanjing (3rd to 5th century): a number leaves 2 when counted by threes, 3 by fives and 2 by sevens. The first two give x ≡ 8 (mod 15), so x is one of 8, 23, 38, 53, 68, 83, 98. Mod 7 these are 1, 2, 3, 4, 5, 6, 0, every remainder once because 15 and 7 are coprime, and only 23 is 2 mod 7 (Demo: three congruences). The answer is x ≡ 23 (mod 105). The construction agrees: M = 105, Mᵢ = 35, 21, 15, yᵢ = 2, 1, 1, and 2·35·2 + 3·21·1 + 2·15·1 = 140 + 63 + 30 = 233 ≡ 23. Solving two at a time and lifting this way works for any number of moduli.
When the moduli are not coprime
Try moduli 2 and 4 (gcd 2). The grid has 2 × 4 = 8 cells, but the walk 0, 1, 2, 3 is back at cell (0, 0) at x = 4, since lcm(2, 4) = 4. Only 4 cells ever fill, each with two numbers (Demo: moduli 2 and 4 are not coprime). An even x always has an even x mod 4, so x mod 4 already decides x mod 2.
| system | cell | solutions in 0…7 |
|---|---|---|
| x ≡ 0 (mod 2), x ≡ 1 (mod 4) | empty | none |
| x ≡ 1 (mod 2), x ≡ 3 (mod 4) | 3, 7 | two: unique only mod 4 |
In general, x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) has a solution exactly when a₁ ≡ a₂ (mod gcd(m₁, m₂)), and then it is unique modulo lcm(m₁, m₂), not modulo the product.
Where it is used
- RSA decryption computes cd mod p and mod q separately (two half-size exponentiations, see Modular Exponentiation and Toy RSA) and combines them with the CRT, about 4 times faster.
- Residue number systems store a big number as its remainders mod several small coprime moduli; addition and multiplication work on each remainder separately.
- Calendars and cycles: two cycles of coprime lengths line up again only after their product (the 60-year Chinese cycle is 10 stems and 12 branches, lcm 60).
See also Sieve of Eratosthenes for primes and Number Bases, another way to write a number as a list of remainders.
What the page leaves out
The page uses tiny moduli so every number fits on the grid, and it finds each inverse by trying 1, 2, … instead of running extended Euclid. Real code combines congruences one pair at a time (Garner's algorithm) to keep the numbers small. The CRT also holds for polynomials and for ideals in rings, and in abstract terms it says that ℤ/15 and ℤ/3 × ℤ/5 are the same ring.