Numbers that wrap

Nine hours after eight o’clock is five o’clock. That is arithmetic, it is correct, and it is not the arithmetic of the whole numbers — in that arithmetic, $8 + 9$ is $17$.

What has been discarded is the number of times the hand passed twelve, and what has been kept is the remainder. That is the whole definition: two numbers are the same modulo $m$ when they differ by a multiple of $m$, and the arithmetic on the dial is the arithmetic of the whole numbers with that identification made.

The interest is not in the definition. It is that the resulting system is well-behaved in one operation and startlingly badly behaved in the other, and that the difference turns on a single property of $m$.

Nothing is lost by wrapping #

The first thing to establish is that the arithmetic is consistent — that the answer does not depend on which representatives are chosen. If $a$ and $a'$ differ by a multiple of $m$, and so do $b$ and $b'$, then $a+b$ and $a'+b'$ differ by a multiple of $m$, and so do $ab$ and $a'b'$. Both are one line of algebra.

That is not a formality. It is the statement that the dial is a structure rather than a notation: addition and multiplication descend from the integers to the residues, so every identity that holds for whole numbers holds on the dial. Commutativity, associativity, distributivity — all inherited, none re-proved.

Addition’s table is a Latin square: every residue appears exactly once in every row and every column. That is the same as saying addition by any fixed amount is a permutation of the dial, which is obvious once seen — adding $k$ rotates the dial by $k$ places and a rotation loses nothing.

So addition is as good as it could be. Every element has an inverse (add $m - k$), the operation is closed, and cancellation works: if $a + c = b + c$ then $a = b$.

Multiplication is a different animal #

Now multiply.

The table is not a Latin square, and the failures are dramatic. Row $6$ reads $0, 6, 0, 6, 0, 6, \ldots$ — it takes two values out of twelve. Row $4$ takes three. And $3 \times 4 = 0$, with neither factor zero.

That last is the one worth naming. In the integers, a product of two non-zero numbers is never zero, and a very large amount of ordinary algebra rests on it: it is why an equation can be solved by factoring, why a polynomial of degree $n$ has at most $n$ roots, and why cancellation works. On a dial of twelve, none of that is safe. The equation $x^2 = 4$ has four solutions modulo $12$ — namely $2$, $4$, $8$ and $10$ — which is more roots than the degree allows.

Numbers like $3$ and $4$ here are zero divisors, and their presence is exactly what makes the dial of twelve a worse place to do algebra than the integers.

The condition is primality #

Which rows are permutations? The multipliers coprime to $m$ — those sharing no factor with it.

The reason is Euclid’s algorithm. If $\gcd(k, m) = 1$, the algorithm produces integers $u, v$ with $ku + mv = 1$, so $ku \equiv 1$ on the dial and $k$ has a multiplicative inverse. Multiplying by something invertible is a permutation. Conversely, if $k$ and $m$ share a factor $d > 1$, then $k \cdot (m/d) \equiv 0$ and $k$ is a zero divisor, which no invertible element can be.

So the count of permutation rows is the count of residues coprime to $m$, which is Euler’s totient function — and the generator computes it and checks the row count against it rather than taking the claim on trust.

Now the punchline. If $m$ is prime, every non-zero residue is coprime to it. So every non-zero row is a permutation, every non-zero element has an inverse, there are no zero divisors, and the dial is a field — a number system in which all four operations work exactly as they do in the rationals.

Twelve and thirteen differ by one and their multiplication tables are different kinds of object. That is the sharpest illustration this site has of what primality actually does: it is not a fact about which numbers are interesting, it is the condition under which arithmetic keeps working.

The gap between the two tables is also a decent answer to a question this site keeps running into: why do the primes matter so much, given that they are defined by a negative property — having no factors? The answer visible here is that the negative property is exactly the absence of the obstruction. A composite modulus has factors, factors give zero divisors, and zero divisors break division. Primes are not special because they are rare or irregular; they are special because they are the moduli with nothing in the way, and their irregular distribution is a separate fact that happens to be true of the same numbers.

Orbits, and a theorem about polygons #

Start at $1$ and keep multiplying by the same number. Since the dial is finite, the sequence must repeat, and since multiplication by an invertible element is reversible, it must return to where it started rather than falling into a cycle it entered from outside.

The number of steps before returning is the order of that multiplier. For a prime dial, the order always divides $m - 1$, which is Fermat’s little theorem in the form $a^{m-1} \equiv 1$, and the generator checks the divisibility on every orbit it draws.

The reason the order divides $m-1$ is worth stating because it is one line and it is a real proof. The orbit of $1$ under multiplication by $a$ is a subgroup, and multiplying that whole orbit by any other residue produces a set of the same size, disjoint or identical. So the non-zero residues split into equal-sized blocks, and the block size divides the total. That is Lagrange’s theorem, in the case where it is easiest to see.

This has a consequence used constantly and worth stating plainly: on a prime dial, exponents can be reduced modulo $m-1$. Computing $2^{1000}$ modulo $13$ needs no large numbers at all, because $1000 = 83 \times 12 + 4$, so the answer is $2^4 = 16 \equiv 3$.

What it costs, and what it buys #

Everything here is cheap. Addition and multiplication on a dial cost one operation and one remainder; exponentiation by squaring costs $\log$ of the exponent. Finding an inverse costs a run of Euclid’s algorithm, which is famously fast — the number of steps is bounded by about five times the digit count, by Lamé’s theorem.

What it buys is the whole of public-key cryptography, and the reason is an asymmetry that has appeared nowhere else in this essay. Exponentiation on a dial is easy. Its inverse — given $a$, $m$ and $a^k \bmod m$, recover $k$ — is the discrete logarithm problem, and nobody knows how to do it quickly for a well-chosen prime. The orbit figures above show why intuition is no help: the star polygon a generator traces visits the residues in an order with no visible relationship to their size, so knowing where a walk ended says nothing about how many steps it took.

That is the honest reason to draw those figures. The scrambling is the security, and it is visible.

Two smaller uses are worth naming because they are everywhere and nobody notices. A hash table is a dial: an index is a key reduced modulo the table size, and the classical advice to make that size prime is exactly the observation above — a composite modulus lets keys sharing a factor with it collide systematically rather than by the birthday coincidence they should. And every check digit scheme, from ISBNs to bank account numbers, is a linear equation on a dial chosen so that the two commonest human errors — a mistyped digit and a transposed pair — both break it.

Where the small cases lie #

The dial of two is the parity that runs through much of this site: even and odd, with $1 + 1 = 0$. It is a field, since two is prime, and it is the smallest one.

It is also profoundly misleading as an example, and worth flagging because it is the case everyone meets first. Modulo two, squaring does nothing ($0^2 = 0$, $1^2 = 1$), addition and subtraction are the same operation, and every non-zero element is its own inverse. All three of those are accidents of smallness that fail at every larger prime, and a reader who forms intuitions on them will find every one of those intuitions broken at three.

Colouring Pascal’s triangle by parity is the same dial in its most spectacular use, and it is worth noting that the fractal there is not a fact about the number two: the same construction modulo three or five produces different and equally structured patterns, governed by Lucas’ theorem, which is a statement about writing numbers in base $p$. Two is where the picture is prettiest, not where the mathematics lives.

Where it fails, and where it goes instead #

The residues modulo a composite $m$ are not a field, and the repair is not to give up but to take the dial apart. If $m = 12 = 3 \times 4$, then knowing a number modulo $3$ and modulo $4$ determines it modulo $12$, and every arithmetic operation can be done in the two smaller dials independently. That is the Chinese remainder theorem, and it says that a composite dial is a product of coprime prime-power dials rather than a damaged version of a prime one.

So the messy multiplication table above is not one bad structure; it is two good ones interleaved, and the zero divisors are the pairs that are zero in one factor and not the other. The structure was never wrong, only badly presented by a single dial.

What genuinely fails is order. The integers are ordered and the residues cannot be: if $1 > 0$ then adding $1$ repeatedly should keep increasing, and on a dial it comes back. So no ordering compatible with addition exists on any finite dial, and everything in mathematics that depends on order — inequalities, limits, calculus — has no analogue here. That is a large amount to give up, and it is the price of finiteness.

The loss is worth measuring against what finiteness gives back. A question about the integers may need an infinite search; the same question on a dial can always be settled by trying every residue, so decidability comes free. Whether $x^2 \equiv 2$ has a solution modulo $7$ is answered in seven multiplications. Whether $x^2 = 2$ has a rational solution is a proof rather than a check, and a famous one.

That trade — order for decidability — is why modular arithmetic is the first thing tried against a hard question about integers. If an equation has no solution on some dial, it has none in the integers, and the dial is checkable. The converse fails, which is what makes the method a filter rather than an answer, and the exact extent of that failure is the local–global problem that a large part of modern number theory is about.

What the picture cannot show #

The dial figures show one modulus at a time, and everything that matters is a comparison across moduli — twelve against thirteen, prime against composite. Two tables side by side is the closest a static figure gets to a statement about all $m$, and it is not close.

The orbit figures show a path closing after a certain number of steps, and the theorem is that the number divides $m - 1$. Divisibility is not a visual property: a twelve-step orbit and a three-step orbit look like a dense polygon and a sparse one, and nothing in either picture says the second number divides the first. The generator checks it; the drawing cannot.

And the discrete logarithm’s hardness is unshowable in the strongest sense. The orbit figure suggests scrambling, and suggestion is not evidence — the problem is believed hard and not known to be, and a picture of thirteen residues is no evidence at all about a modulus with six hundred digits.

The ladder from here #

Rungs above: the Chinese remainder theorem drawn as a lattice. Euler’s totient function and its multiplicativity. Primitive roots, and which dials have them. Quadratic residues and the reciprocity law, which is the deepest elementary fact about these dials. Fermat’s little theorem as a necklace-counting argument, where the divisibility becomes a statement about beads. The RSA construction, and the exact point at which its security is a conjecture rather than a theorem. Finite fields of prime-power order, which are not dials at all. And modular forms, where the word starts meaning something else entirely.

The lesson is about what a definition includes #

The dial was introduced as a convenience — a way of talking about remainders — and it arrived carrying a complete algebraic structure that nobody put there.

That is the recurring experience of the subject and it is worth naming. A definition made for one reason turns out to determine a great deal that the definition never mentioned: that addition is a rotation, that multiplication’s behaviour depends on the factorisation of the modulus, that a finite system cannot be ordered, that exponentiation is easy and its inverse may not be. None of that was decided. All of it was implied by identify numbers that differ by a multiple of $m$, and the work of the subject is finding out what was implied.

The same thing happens whenever an identification is made rather than a construction performed. Gluing the ends of a strip after a half-turn is a one-sentence instruction that determines one-sidedness, one edge, and what happens when the result is cut. Adding a single point to the plane determines that circles and lines become one kind of object. In each case the definition is short and the consequences are not, and there is no way to read the consequences off the definition except by working them out.

Gauss, who set all this out in the Disquisitiones Arithmeticae of 1801 and invented the $\equiv$ notation for it at twenty-four, was explicit that the notation was the point — it was chosen to look like equality so that the identities of ordinary arithmetic could be written down unchanged and used without re-derivation. That is the same design decision Leibniz made about the integral sign, and it worked for the same reason.