Two dials at once

A number leaves a remainder on division by three and another on division by five. Neither remainder says much. Together they say everything, at least up to fifteen.

Counting $0, 1, 2, 3, \ldots$ moves one step down and one step across at every tick, wrapping at each edge. After fifteen steps both dials are back where they started and the walk repeats. In between it has visited every cell exactly once.

That is the Chinese remainder theorem in the case that matters most: a pair of remainders modulo coprime numbers names a unique residue modulo their product.

Where the coprimality enters #

The theorem is not about every pair of moduli, and the failure is as visible as the success.

Both dials advance together, so a number’s remainder modulo two is determined either way — from the modulo-four reading and from the modulo-six reading — and the two must agree. Half the cells describe a number that is even according to one dial and odd according to the other, and no such number exists.

The general statement is that the walk reaches $mn/\gcd(m,n)$ cells, which is the least common multiple, and fills the grid exactly when the gcd is one. Both figures check that count off their own walk rather than quoting the formula.

Counting the grid two ways #

The proof is a count, made twice.

Count one. The residues modulo $mn$ number $mn$. Each of them determines a pair of remainders, so there is a map from a set of size $mn$ into the grid.

Count two. The grid has $m$ rows and $n$ columns, so $mn$ cells.

The map is injective when $m$ and $n$ are coprime: if two numbers give the same pair, their difference is divisible by both $m$ and $n$, hence by $mn$, so they are the same residue modulo $mn$. An injective map between two finite sets of the same size is a bijection, so it is also surjective — every pair occurs.

That last step is the whole trick and it is worth naming: surjectivity was obtained for free from injectivity and a count. Nothing was constructed. The theorem asserts that a number with any prescribed pair of remainders exists, and the proof never produces one.

Producing one takes Euclid’s algorithm. Since $\gcd(m, n) = 1$ there are whole numbers with $um + vn = 1$; then $x = a\,vn + b\,um$ has remainder $a$ modulo $m$ and $b$ modulo $n$, as substituting shows. The existence proof and the construction are separate pieces of work, which is the same division of labour that runs through this whole field.

The construction is worth reading once more for what it is doing, because it is a pattern rather than a formula. The number $vn$ is $1$ modulo $m$ and $0$ modulo $n$; the number $um$ is the reverse. So the two of them are indicator numbers — each one switches on one dial and off the other — and the answer is built by scaling each indicator by the remainder it is meant to produce and adding. Anybody who has built a function from a basis will recognise the move: this is interpolation, with the residues as coordinates and the indicators as a basis.

The recognition is not decorative, because the same argument with polynomials gives Lagrange interpolation, and with power series it gives partial fractions. The Chinese remainder theorem is one instance of a general fact about splitting a ring into independent pieces, and every instance is proved by exhibiting the indicators.

What it is for #

Splitting a modulus into coprime pieces turns one calculation into several smaller ones, and the smaller ones are independent.

Arithmetic modulo $3 \times 5 \times 7 \times 11 \times 13 = 15015$ can be done as five separate calculations on dials of at most thirteen, with the answers reassembled at the end. Each small calculation fits in a machine word, none of them interacts with the others, and all five can run at once. That is the residue number system, and it is used where multiplication is expensive and carries are the bottleneck — signal processing hardware, and the internals of cryptographic libraries.

The gain in RSA is concrete. Decryption raises a number to a large power modulo $n = pq$; doing it modulo $p$ and modulo $q$ separately and recombining is about four times faster, since the cost of modular exponentiation grows faster than linearly in the size of the modulus. The private key holder knows $p$ and $q$ and can do this; an attacker knows only $n$ and cannot.

The same split has a cost worth stating, because it is the reason residue arithmetic is not used everywhere. Addition, subtraction and multiplication go through the pieces without interaction, and comparison does not: deciding which of two numbers is larger from their remainders requires reassembling them, because the grid has no order on it. Nor does division, nor does detecting overflow. A system that makes multiplication trivial and comparison expensive is worth having only where the multiplications outnumber the comparisons, which in signal processing they do and in general-purpose computing they do not.

There is a second use, quite different in character. Because a number is determined by its remainders, a function on a large modulus is determined by its behaviour on the small ones — so a question about $\mathbb{Z}/n$ reduces to the same question about $\mathbb{Z}/p^e$ for each prime power in $n$. That reduction is why multiplicative functions are studied on prime powers, and why nearly every theorem in this field is proved for a prime and then assembled.

Where the split is doing the arguing #

Two applications are worth setting out in full, because in both of them the theorem is not a computational convenience but the whole argument.

Counting solutions. How many solutions does $x^2 \equiv 1 \pmod{105}$ have? Since $105 = 3 \times 5 \times 7$, the theorem says a solution modulo $105$ is precisely a triple of solutions, one for each prime. On a prime dial, $x^2 = 1$ has exactly two solutions, $\pm 1$ — because $x^2 - 1 = (x-1)(x+1)$ and a prime dividing a product divides a factor. So there are $2 \times 2 \times 2 = 8$ solutions modulo $105$, and the count is a product because the choices are independent.

That is a general method. The number of solutions of a congruence modulo $n$ is multiplicative in $n$, so counting is done prime by prime and multiplied. The property is not obvious from the congruence and is immediate from the grid.

Euler’s totient. The count of residues coprime to $n$ is multiplicative for the same reason: a residue is coprime to $mn$ exactly when it is coprime to $m$ and to $n$, so the coprime residues correspond to pairs of coprime residues, and $\varphi(mn) = \varphi(m)\varphi(n)$ for coprime $m$ and $n$. The formula $\varphi(n) = n\prod(1 - 1/p)$ follows by working out $\varphi(p^e)$ once and multiplying.

Both arguments have the same shape, and it is the shape this whole essay is about: a question on a composite dial is a question on each prime-power dial, asked separately, with the answers multiplied. Nothing in the original question suggests it can be taken apart, and the grid is what shows that it can.

The oldest version #

The theorem’s name is literal. Sun Zi’s Mathematical Manual, from somewhere in the third to fifth century, poses the problem: a number leaves remainder two on division by three, three on division by five, and two on division by seven; what is it?

The answer given is twenty-three, along with a recipe — multiply the first remainder by seventy, the second by twenty-one, the third by fifteen, add, and subtract multiples of a hundred and five. The recipe is exactly the construction above: seventy is the number that is one modulo three and zero modulo the others, and so on.

No proof accompanies it, and no statement of the general theorem. What is there is a worked method that happens to be correct for every case, presented as an answer to one question about counting soldiers. Qin Jiushao gave the general algorithm in 1247, including the case of moduli that are not pairwise coprime, and Gauss stated and proved it in the Disquisitiones in 1801, apparently unaware of either.

The gap between a correct recipe and a stated theorem is the recurring theme of pre-modern mathematics, and it is the same gap the Babylonian triple tablet leaves open. A method that works is evidence that somebody understood something; it is not a record of what they understood.

Sun Zi’s problem is also the earliest surviving example of a genre that has never gone away: the puzzle whose answer requires the theorem and whose statement conceals it. Counting an army by lining the soldiers up in rows of three, five and seven and recording the remainders is a genuinely practical method for a commander who cannot count past a few hundred, and it is the same computation a processor performs when it does modular exponentiation in two halves. What changed in seventeen centuries is the size of the numbers and the reason for wanting them, not the arithmetic.

What the picture cannot show #

The grids drawn here are small enough to fill in by hand, and every use of the theorem is on numbers that are not.

More interestingly, the picture shows the theorem for two moduli and the useful version handles many. Extending is straightforward — apply it repeatedly, combining two moduli at a time — but the drawing does not extend, because three moduli need a three-dimensional grid and five need five dimensions. The reasoning survives the loss of the picture, as it did for the divisor lattice, and again what survives is a product of independent choices.

The figures also hide a distinction that matters for the applications. The theorem gives a bijection between residues and pairs of residues, and it gives more: the bijection respects addition and multiplication, so it is an isomorphism of rings rather than merely a matching of sets. Nothing in a grid of cells shows that, because the grid has no arithmetic drawn on it. The fact that the two structures are the same, and not merely the same size, is what makes the parallel computation valid, and it is entirely invisible in the figure.

The calendar, and a cicada #

Two everyday systems are the theorem in use, and one of them is not human.

The Julian day count and the Western calendar together make a period of $28 \times 19 \times 15 = 7980$ years — the solar cycle of $28$, the Metonic lunar cycle of $19$ and the Roman indiction of $15$, all pairwise coprime — and any triple of positions in those three cycles occurs exactly once in that span. Scaliger proposed it in 1583 for exactly the reason the theorem gives: three readings pin down a year without ambiguity, which is what a chronologist comparing sources needs.

The biological case is the same statement read backwards. Periodical cicadas emerge every $13$ or $17$ years, both prime, and the standard explanation is a coprimality argument: a predator with a cycle of $k$ years coincides with a prey cycle of $p$ years once every $\mathrm{lcm}(p, k)$ years, and a prime $p$ makes that least common multiple as large as it can be. A cicada on a $12$-year cycle would meet a $2$-, $3$-, $4$- or $6$-year predator constantly; one on a $13$-year cycle meets a $4$-year predator once in fifty-two years.

The grid in the second figure above is the picture of the bad case, and the first figure is the picture of the good one. Whether the cicada explanation is correct is disputed — the evidence for the predators is thin — but the mathematics it appeals to is exactly the count in those two drawings, and the reasoning is sound whatever the biology turns out to be.

Where the walk goes on a torus #

The diagonal walk in the first figure has a second reading that is not about numbers at all.

Glue the grid’s edges: left to right and top to bottom, making a torus. The walk is then a straight line of slope one on that torus, and the question of whether it fills the grid is the question of whether a straight line on a torus closes up or covers everything. For whole-number slopes it closes; for irrational slopes it never closes and passes arbitrarily close to every point.

That is exactly the picture behind the way an irrational rotation spreads out, and the coprimality condition here is the finite version of the irrationality condition there. A line closes early when the ratio of the sides simplifies, and spreads out when it does not — which is the same statement about resonance that decides whether two orbiting bodies lock together.

So the Chinese remainder theorem and the theory of rational approximation are the discrete and continuous halves of one question about lines on a torus, and the shared object is the greatest common divisor: a number in the first case, and a continued fraction in the second.

Where the ladder goes next #

This is the second rung on the modular arithmetic ladder. The first established the dial and found that multiplication behaves well only for a prime modulus; this one splits a composite modulus into prime pieces, which is why the first rung’s restriction is not a limitation in practice.

What comes next is the question the pieces raise: on a prime dial, which residues are squares? Half of them are, and deciding which requires knowing about a second prime — that is quadratic reciprocity, and its proof counts the lattice points in a rectangle in two directions, which is the same move this essay used on a grid.