Multiplying every number on the dial at once

Numbers that wrap followed a single number round a dial as it was multiplied by 2 over and over: $1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7$ and back to $1$ on a dial of thirteen. That is one orbit, traced from one starting point. Multiplication by 2 does something to every residue at once, and the natural picture of that is not a path but a map: every point on the dial joined to the point it is sent to.

Draw it and something appears that no single orbit shows. On a large dial the chords from $k$ to $2k$ crowd together along a heart-shaped curve with one cusp, and the chords from $k$ to $3k$ along a kidney-shaped curve with two. Each multiplier has its own curve, and the curve has exactly one cusp fewer than the multiplier. This essay explains the curve, and on the way finds that the picture holds three separate pieces of arithmetic: when multiplication is reversible, how it splits the dial into cycles, and why those cycles are necklaces.

A small dial first, and a collapse #

On a dial small enough to read, the chords can be followed one at a time. With twenty-four places and the multiplier 2, residue $1$ goes to $2$, $5$ to $10$, $13$ to $26 \equiv 2$, and $20$ to $40 \equiv 16$.

The chords land only on even residues, and each even residue receives two of them: $1$ and $13$ both go to $2$, $5$ and $17$ both go to $10$. The reason is that $2 \times 12 = 24 \equiv 0$, so adding $12$ to anything does not change its double. Multiplying by $m$ on a dial of $N$ collapses the dial onto $N/\gcd(m, N)$ residues, each hit $\gcd(m, N)$ times, and the collapse is visible as pairs of chords converging.

When $m$ and $N$ share no factor the collapse vanishes. Then $m$ has an inverse on the dial — a number that undoes multiplication by $m$, found by running Euclid’s algorithm backwards — and so multiplication by $m$ can be undone, which means no two residues go to the same place. The chords are then a permutation of the dial: every residue sends one chord out and receives exactly one. On the dial of 199 in the first figure that is automatic, since 199 is prime.

A permutation splits into cycles #

A permutation of a finite set, followed from any starting point, must eventually return, because there are only finitely many places to go and nowhere is visited twice without closing a loop. So the permutation breaks the dial into disjoint cycles. For multiplication those cycles have lengths that can be predicted from the arithmetic alone.

The cycle through $1$ is $1, 2, 4, 8, 16, 11$ and back, of length $6$ — the smallest number of doublings that returns $1$ to itself, which is the order of $2$ modulo $21$. Every residue that shares no factor with $21$ lies on a cycle of exactly that length, because the cycle through $k$ is just the cycle through $1$ multiplied by $k$, and multiplying by $k$ is itself a permutation of those residues. So the twelve residues coprime to $21$ fall into two cycles of six.

That observation is Euler’s theorem, drawn. The residues coprime to $N$ — there are $\varphi(N)$ of them, twelve on the dial of twenty-one — are cut by the permutation into cycles that all have the same length, the order of $m$. Cycles of equal length that exactly fill a set of twelve must have a length that divides twelve. So the order of $m$ divides $\varphi(N)$, and multiplying by $m$ a full $\varphi(N)$ times returns every unit to itself: $m^{\varphi(N)} \equiv 1$. On a prime dial, where $\varphi(p) = p - 1$, it is Fermat’s little theorem, and the proof is a count of polygons of equal size.

The other residues behave like residues on a smaller dial. The multiples of $3$ — $3, 6, 9, 12, 15, 18$ — are three times the residues of a dial of seven, and doubling them is doubling on that dial, where $2$ has order $3$. So they fall into two cycles of three. The multiples of $7$ — $7$ and $14$ — are seven times the residues of a dial of three, where $2$ has order $2$, and they swap. Zero is fixed. In general, the residue $k$ lies on a cycle whose length is the order of $m$ modulo $N/\gcd(k, N)$, and every such length divides the order of $m$ modulo $N$ itself. The figure checks both statements on every cycle it draws.

Counted up, the number of cycles is a sum over the divisors $d$ of $N$: each divisor contributes the residues whose “own dial” has size $d$ — there are $\varphi(d)$ of them — in cycles of length equal to the order of $m$ modulo $d$. That formula looks like a curiosity, and it is the formula for counting necklaces.

Doubling on a dial of $2^n - 1$ turns necklaces #

Take the dial of $2^n - 1$ and write each residue in binary with exactly $n$ digits. Doubling a number shifts its binary digits one place to the left, and on this dial the digit that falls off the top reappears at the bottom, because $2^n \equiv 1$. So doubling modulo $2^n - 1$ is rotation of an $n$-bit string, and its cycles are the sets of strings that are rotations of one another — the necklaces.

On the dial of fifteen the cycles are the rotation classes of four-bit strings: $\{1, 2, 4, 8\}$ are $0001, 0010, 0100, 1000$; $\{3, 6, 12, 9\}$ are $0011$ and its rotations; $\{5, 10\}$ are $0101$ and $1010$, a necklace with only two distinct rotations; $\{7, 14, 13, 11\}$ are the strings with three ones. The sixth binary necklace of length four, $1111$, is fifteen, which the dial identifies with $0000$. So the count of cycles, five, is the count of binary necklaces, six, less one.

The count works at every length. The number of binary necklaces of length $n$ is $\frac1n\sum_{d\mid n}\varphi(d)\,2^{n/d}$ — each rotation class counted by averaging, over the $n$ rotations, the number of strings each rotation leaves unchanged — and doubling modulo $2^n - 1$ has exactly one cycle fewer than that. On the dial of $31$ there are $7$ cycles and $8$ necklaces of length five; on $63$, $13$ cycles and $14$ necklaces of length six; on $255$, $35$ and $36$; on $1023$, $107$ and $108$. The one necklace lost is always the same: the string of all ones, which the dial cannot tell from the string of all zeros.

That identification is what makes the arithmetic of necklaces and the arithmetic of multiplicative orders the same subject. Fermat’s little theorem proved by counting necklaces runs the correspondence in one direction; the cycle count above runs it in the other. And the necklace that returns after fewer than $n$ rotations, like $0101$, is a residue whose own dial is smaller: $5$ shares the factor $5$ with $15$, and on the dial of three, doubling has order $2$.

The curve the chords crowd onto #

On a dial of a few hundred places the chords stop reading as individual lines and start reading as a shape, and the shape is the envelope of the family: a curve that touches every chord. It is easiest to find by letting the dial become a continuous circle, with a chord from each angle $\theta$ to the angle $m\theta$.

Put the circle in the complex plane, so the chord joins $e^{i\theta}$ to $e^{im\theta}$. The point

$$P(\theta) = \frac{m\,e^{i\theta} + e^{im\theta}}{m + 1}$$

is a weighted average of the chord’s two ends, so it lies on the chord, a fraction $1/(m+1)$ of the way from $e^{i\theta}$ towards $e^{im\theta}$. Differentiating, $P'(\theta)$ is a multiple of $i\big(e^{i\theta} + e^{im\theta}\big)$, and for two points on the unit circle the sum of their positions is perpendicular to their difference, so $i\big(e^{i\theta} + e^{im\theta}\big)$ runs along the chord. The curve $P$ therefore touches every chord where it crosses it: $P$ is the envelope. The figures check both facts — on the chord, and along it — at a spread of chords.

$P$ is an epicycloid: the path of a point on a small circle rolling round the outside of a larger one. Its cusps are where it stops moving, where $P'(\theta) = 0$, which needs $e^{i\theta} = -e^{im\theta}$ — the chord’s two ends diametrically opposite — or $e^{i(m-1)\theta} = -1$. That happens $m - 1$ times round the circle. So the chords from $k$ to $mk$ envelope an epicycloid with $m - 1$ cusps: one for doubling, the cardioid; two for tripling, the nephroid; and one more for each step up.

The small multiples make the pattern plain, and they show something the formula does not dwell on: a residue $k$ with $mk \equiv k$ gives a chord of length zero, and those fixed points are where the chords are shortest and densest, near the cusps. On a dial of $N$ there are $\gcd(m - 1, N)$ of them, since $(m - 1)k$ must be a multiple of $N$.

The same curve is drawn by light in a cup #

The envelope has a physical reading that makes the multiplication tables less arbitrary than they look. A ray of light inside a circular mirror, travelling along a chord from angle $\alpha$ to angle $\beta$, reflects off the mirror and leaves along the chord to $2\beta - \alpha$: the angle of incidence equals the angle of reflection, and on a circle that is a statement about arcs.

Put a point source of light on the rim at angle $0$. A ray that first strikes the mirror at angle $\theta$ reflects along the chord from $\theta$ to $2\theta$. The reflected rays are the chords of the doubling table, and where they crowd together the light is brightest: the bright curve, the caustic, is the cardioid. With the source infinitely far away instead, so that the incoming rays are parallel, the reflected chords run from $\theta$ to $3\theta$ plus a fixed half-turn, and the caustic is the two-cusped nephroid — the bright curve that sunlight draws on the surface of coffee in a round cup.

That is the same family of curves, drawn by the same geometry, that a billiard ball in a round table traces out as its caustic circle when it keeps bouncing at a fixed angle. There the chords are $\theta \to \theta + c$, all the same length, and the envelope is a circle; here they are $\theta \to m\theta$, of every length, and the envelope has cusps.

The dial is a window onto a chaotic map #

There is one more reading of the chords, and it connects the dial to dynamics. Divide every residue by $N$ and the dial of $N$ becomes the $N$ equally spaced fractions $0, 1/N, \ldots, (N-1)/N$ on a circle of circumference one. Multiplying by $m$ modulo $N$ becomes multiplying the fraction by $m$ and discarding the whole part — the map $x \mapsto mx \bmod 1$ on the circle.

That map, for $m = 2$, is the doubling map, one of the simplest chaotic systems there is: it doubles every distance, its orbits are the binary expansions of $x$ read one digit at a time, and almost every orbit wanders over the whole circle with no pattern. The fractions with denominator $N$ are a finite set it maps to itself, and on them every orbit is periodic. So the cycles drawn on the dial are periodic orbits of a chaotic map, and the periodic orbits of the doubling map are exactly the fractions with odd denominators, since those are the ones whose binary expansions repeat. The dial of fifteen shows the periodic points of period dividing four; the dial of twenty-one, those whose periods divide six.

Seen that way, the chord pictures show both halves of the doubling map’s character. The cycles are its orderly part, the periodic orbits, finitely many at each denominator. The envelope is its disorderly part: as $N$ grows the chords fill in densely, every residue’s image lies far from the residue itself, and nothing in the picture stays still except the one fixed point the cusp marks.

What the chords cannot show #

They cannot show the envelope exactly. On a finite dial there are finitely many chords, and the dashed curve is drawn from its formula, not traced from the chords. The chords approach it as the dial grows, and the figures check that the formula’s curve touches every chord it is compared with; they do not, and cannot, show a limit.

They cannot show which multipliers generate. Whether some $m$ has a single cycle through all the units — a primitive root — is visible only as a cycle of full length in a picture like the one on the dial of twenty-one, and the question of which dials have such an $m$ is a theorem about counting that no chord picture decides.

And they cannot show large dials’ cycles. On a dial of 199 the cycles of doubling have length 99, the order of $2$ modulo $199$, and the two long cycles are drawn together as one tangle of chords. The cycle structure is computed and checked; it is only legible on small dials.

Where the dials go next: powers of one prime #

The cycle lengths are orders, and orders behave in a striking way on dials whose size is a power of a single prime. On a dial of three, doubling has order $2$; on a dial of nine, order $6$; on twenty-seven, $18$; on eighty-one, $54$; on two hundred and forty-three, $162$. Each step up the powers of three multiplies the order by three. The doubling chords on a dial of $3^k$ form one long cycle through every residue coprime to three, and that cycle grows by a factor of three each time the dial does.

The reason is one line of the binomial theorem. Suppose $2^r$ is $1$ on the dial of $3^k$, so that $2^r = 1 + 3^k t$ for some whole number $t$. Cubing,

$$2^{3r} = (1 + 3^k t)^3 = 1 + 3^{k+1} t + 3^{2k+1} t^2 + 3^{3k} t^3,$$

and every term after the $1$ is a multiple of $3^{k+1}$. So $2^{3r}$ is $1$ on the next dial up. The order there is therefore a divisor of $3r$ and a multiple of $r$ — since anything that is $1$ on the larger dial is $1$ on the smaller — which leaves exactly two possibilities: it stays $r$, or it becomes $3r$. It stays only if $2^r$ was already $1$ on the dial of $3^{k+1}$, which is a coincidence of one extra digit, and the same argument works for every odd prime in place of three. For most primes and most multipliers the order multiplies at every step. The rare primes where it stalls at the first step are the subject of two primes where Fermat holds twice, and they are genuinely rare: for the multiplier 2, only two are known.

The same lifting, done not to orders but to roots — solving an equation on a dial of $p$ and then on $p^2$, $p^3$ and beyond, one digit at a time — is where the next essay goes. It turns a finite dial into an infinite sequence of ever finer dials, and the sequence into a new kind of number.

One map, drawn whole #

Multiplying by $m$ on a dial of $N$, drawn as a chord from every residue to its multiple, is a two-to-one collapse wherever $m$ shares a factor with $N$ and a permutation where it does not. The permutation breaks the dial into cycles whose lengths are the orders of $m$ on the dial and on the smaller dials of its divisors, and on the dial of $2^n - 1$ doubling rotates binary strings, so its cycles are the necklaces.

As the dial grows the chords crowd onto an epicycloid with $m - 1$ cusps, the curve a point on a rolling circle traces, because the point a fraction $1/(m+1)$ of the way along each chord moves along the chord itself. The same curves are the caustics of light reflected in a circle, and the same cycles are the periodic orbits of the chaotic map $x \mapsto mx \bmod 1$.

Drawing a map whole, rather than following one point through it, turns its algebra into geometry — and the geometry keeps turning up elsewhere.