The Chinese Remainder Theorem

A puzzle from the Sunzi Suanjing ("Master Sun's Mathematical Manual"), a Chinese text from around the 3rd–5th century: "I have a number of things, but I do not know exactly how many. If I count them by threes, I have two left over. If I count them by fives, I have three left over. If I count them by sevens, I have two left over. How many things are there?"

At first glance this looks hopeless — three different counting schemes, three different leftovers, and infinitely many numbers to check. But it isn't hopeless at all. Whenever the moduli involved (here 3, 5, and 7) share no common factors, a system like this is guaranteed to have exactly one answer within a certain range — no trial and error required, just a short recipe. That guarantee, and the recipe behind it, is the Chinese Remainder Theorem (CRT), and it's over a thousand years older than the algebra we now use to describe it.

Systems of simultaneous remainder conditions turn up any time several independent cycles run at once: gears of different tooth-counts on the same axle, calendars that track days of the week and days of the month, or — as you'll see later on this page — cryptographic hardware splitting one hard computation into several easy ones. The Chinese Remainder Theorem is the reason all of these situations behave predictably instead of chaotically.

The guarantee

Let n_1, n_2, \dots, n_k be pairwise coprime moduli (no two of them share a common factor greater than 1), with product N = n_1 n_2 \cdots n_k. Then the system of congruences

x \equiv a_1 \!\!\pmod{n_1}, \quad x \equiv a_2 \!\!\pmod{n_2}, \quad \dots, \quad x \equiv a_k \!\!\pmod{n_k}

In other words: however many separate remainder conditions you throw at x, as long as the moduli are pairwise coprime, they never contradict each other, and together they pin x down to exactly one value in every block of N consecutive numbers. Because the moduli share no factors, their lcm is simply their full product N, and that product is the length of the pattern before it repeats.

"Unique modulo N" is worth pausing on. It doesn't mean there is literally one number in existence satisfying all three conditions — 23, 128, 233, and every 23 + 105k all work. It means every solution lands in the same residue class mod 105, so once you've found one, you know every other one for free — just add or subtract multiples of N.

This is exactly the same theorem whether you meet it in 3rd-century China solving counting puzzles, or centuries later when European mathematicians such as Gauss rediscovered and formalised it for modular arithmetic — the underlying fact about coprime moduli doesn't care which century or which language describes it.

The recipe

Here is the general construction. For each i, let N_i = N / n_i — the product of all the other moduli. Because N_i is built entirely from numbers coprime to n_i, it is itself coprime to n_i, so it has a modular inverse M_i \equiv N_i^{-1} \pmod{n_i}. The solution is then

x \equiv \sum_{i=1}^{k} a_i\, N_i\, M_i \pmod{N}.

Why does this work? Look at a single term, a_i N_i M_i. Modulo n_i, the factor N_i M_i was built to equal exactly 1 — so the term contributes a_i, exactly what's needed. Modulo every other modulus n_j, though, N_i contains a factor of n_j and so vanishes completely. Every term "speaks" to exactly one congruence and stays silent for all the others — add them up, and each condition is satisfied simultaneously.

Warm-up: two congruences

Before tackling three moduli at once, solve a smaller version: x \equiv 1 \pmod 4 and x \equiv 2 \pmod 5. Here N = 4 \times 5 = 20, N_1 = 5, and N_2 = 4.

x \equiv 1 \cdot 5 \cdot 1 \;+\; 2 \cdot 4 \cdot 4 \;=\; 5 + 32 = 37 \equiv 17 \pmod{20}.

Check it directly: 17 = 4\times4+1, so 17 \equiv 1 \pmod 4 — correct. And 17 = 5\times3+2, so 17 \equiv 2 \pmod 5 — correct too. One clean formula, one clean answer, no guessing.

Worked example: solving Sunzi's puzzle

Now the real thing: x \equiv 2 \pmod 3, x \equiv 3 \pmod 5, x \equiv 2 \pmod 7. The moduli 3, 5, 7 are pairwise coprime, so N = 3 \times 5 \times 7 = 105. The complementary products are N_1 = 35, N_2 = 21, N_3 = 15.

x \equiv 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 \pmod{105}.

Reduce: 233 = 2 \times 105 + 23, so x \equiv 23 \pmod{105}. Check every condition at once: 23 = 3(7)+2, 23 = 5(4)+3, 23 = 7(3)+2 — all three remainders match. Sunzi's answer, smallest positive form, is 23 things (and every 105-th number after it, 128, 233, \ldots, works too).

Here is the whole recipe as a general-purpose function, checked against both examples above:

function egcd(a: number, b: number): [number, number, number] { if (b === 0) return [a, 1, 0]; const [g, x1, y1] = egcd(b, a % b); return [g, y1, x1 - Math.floor(a / b) * y1]; } function modInverse(a: number, m: number): number { const [, x] = egcd(((a % m) + m) % m, m); return ((x % m) + m) % m; } function crt(remainders: number[], moduli: number[]): number { const N = moduli.reduce((product, n) => product * n, 1); let x = 0; for (let i = 0; i < moduli.length; i++) { const Ni = N / moduli[i]; const Mi = modInverse(Ni, moduli[i]); x += remainders[i] * Ni * Mi; } return ((x % N) + N) % N; } console.log(crt([2, 3, 2], [3, 5, 7])); // 23 — Sunzi's puzzle console.log(crt([1, 2], [4, 5])); // 17 — the warm-up

The deeper meaning

CRT is really saying something structural: a number modulo N is completely determined by its remainders modulo the coprime pieces of N, and every combination of remainders is achievable. Written as a splitting of number systems:

\mathbb{Z}_{n_1 n_2 \cdots n_k} \;\cong\; \mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2} \times \cdots \times \mathbb{Z}_{n_k}.

One big, tangled-looking modular world is secretly the same as several small, independent ones, glued together. That "divide one hard problem into several easy ones" pattern turns out to be useful far beyond puzzles: it underlies secret-sharing schemes, lets big modular computations be split into small parallel pieces, and — as the next vignette shows — makes real cryptographic hardware measurably faster.

The clean "exactly one solution" guarantee only holds when the moduli are pairwise coprime. Drop that condition and the recipe above no longer applies — the computation of N_i^{-1} \pmod{n_i} can simply fail, because an inverse might not exist.

Take x \equiv 1 \pmod 4 and x \equiv 2 \pmod 6. The moduli 4 and 6 share a factor of 2, so they are not coprime. Check consistency on that shared factor: the first congruence forces x to be odd (x \equiv 1 \pmod 2), while the second forces x to be even (x \equiv 2 \equiv 0 \pmod 2). No number can be both — this system has no solution at all, and no amount of hunting will turn one up.

Change the numbers slightly — say x \equiv 1 \pmod 4 and x \equiv 3 \pmod 6 — and both congruences agree that x is odd, so a solution does exist (x \equiv 9 \pmod{12}), but it is unique only modulo the lcm 12, not the plain product 24 — the tidy formula from pairwise-coprime moduli needs real repair work here. Moral: always check that the moduli are pairwise coprime before reaching for the standard CRT recipe.

This isn't just theory tucked away in a textbook — it's inside almost every implementation of RSA running today. An RSA private key is built from two large primes p and q, and decrypting a message means computing something like m^{d} \bmod pq, where d and pq can both have hundreds of digits.

Instead of doing that one enormous computation, real systems use CRT to split it into two much smaller ones: compute m^{d} \bmod p and m^{d} \bmod q separately — each with numbers roughly half the size — and then stitch the two partial answers back together with exactly the CRT recipe from this page. Because the cost of modular arithmetic grows faster than the size of the numbers, two half-sized computations finish considerably faster than one full-sized one — a speed-up of roughly four times in practice, for free, just by using the structure CRT reveals.

See it explained