Necklaces that prove a theorem

Fermat’s little theorem says that for a prime $p$ and any whole number $a$, the quantity $a^p - a$ is divisible by $p$. Stated that way it is a fact about remainders and there is no obvious reason for it. Stated as a count, it is a fact about jewellery.

There are $2^5 = 32$ strings. Two of them are constant. The remaining thirty are sorted into six groups of five. So $32 - 2 = 30$ is a multiple of $5$, which is $a^p - a$ divisible by $p$ for $a = 2$ and $p = 5$.

Nothing in that argument used a property of $2$ or of $5$ except that $5$ is prime, and that is the theorem.

Why the groups have exactly $p$ members #

Rotating a string of $p$ beads gives $p$ strings, possibly with repeats. The question is when repeats happen.

Suppose rotating a string by $k$ places returns it, for some $k$ between $1$ and $p-1$. Then rotating by $k$ again returns it, and again; so rotating by any multiple of $k$ returns it. The multiples of $k$ modulo $p$ run through every residue, because $p$ is prime and $k$ is not a multiple of it — that is what makes a prime dial different. In particular rotating by one place returns the string, which means every bead equals its neighbour, which means the string is constant.

So a non-constant string has no rotation that fixes it except the trivial one, its group has exactly $p$ members, and the $a^p - a$ non-constant strings divide evenly into groups of $p$.

The primality is doing exactly one job, and it is worth isolating. With $p = 4$ the string 1010 is fixed by a rotation of two, so its group has two members instead of four, and the count breaks: $2^4 - 2 = 14$ is not a multiple of $4$. The theorem is false for composite exponents and the drawing shows precisely where.

Counting one collection two ways #

The argument is an instance of the most productive move in this field, which is to count a set by two methods and set the answers equal.

Count one: the strings, directly. There are $a$ choices for each of $p$ positions, so $a^p$ of them.

Count two: by group. Each constant string is its own group, giving $a$ groups of size one. Every other group has size $p$. So the total is $a + p \cdot (\text{number of mixed groups})$.

Equating, $a^p = a + p N$, hence $p \mid a^p - a$. The number $N = (a^p - a)/p$ is not a leftover; it is the number of genuinely distinct necklaces, and its being a whole number is the theorem.

That both counts are of the same objects is the entire proof. There is no algebra, no induction, and no modular arithmetic in it — the divisibility appears because a set has been partitioned into pieces of equal size, which is what divisibility means.

The other proof, and what it costs #

Fermat’s little theorem is usually proved a different way, and comparing the two is instructive.

The standard argument: for $a$ not divisible by $p$, the multiples $a, 2a, 3a, \ldots, (p-1)a$ are, modulo $p$, a rearrangement of $1, 2, \ldots, p-1$. Multiplying them together gives $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$, and cancelling the factorial — legitimate because $p$ is prime, so nothing below $p$ shares a factor with it — gives $a^{p-1} \equiv 1$.

That proof is shorter and it hides where the primality enters. The necklace argument puts it in one place: a rotation class has $p$ members unless the string is constant. The algebraic argument puts it in two: the multiples permute the residues, and the factorial cancels. Both are correct; only one of them can be drawn.

The generalisation, and where it leads #

Once the theorem is seen as a count of orbits, the generalisation writes itself: the argument never really needed $p$ to be prime, only that every non-trivial rotation moves every non-constant string.

Replacing rotations by an arbitrary finite group acting on a finite set gives the orbit-counting theorem, and the special case where all the orbits have equal size is the one above. Replacing the prime modulus by any modulus gives Euler’s theorem, $a^{\varphi(n)} \equiv 1 \pmod n$ for $a$ coprime to $n$, where $\varphi$ counts the residues coprime to $n$ — and $\varphi(p) = p - 1$ recovers Fermat’s.

Lagrange’s theorem, that the order of a subgroup divides the order of the group, is the same statement again with the necklaces removed: the orbits are cosets, they have equal size, and the total is a multiple. The chain from a picture of beads to a theorem about groups is short, and every step of it is the observation that equal pieces divide a whole.

Euler’s version is the one that gets used, and it is the reason RSA works. Encryption raises a message to a public exponent $e$ modulo $n = pq$; decryption raises the result to a second exponent $d$ chosen so that $ed \equiv 1 \pmod{\varphi(n)}$. Then $m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m$, by Euler’s theorem, and the message comes back. Computing $\varphi(n) = (p-1)(q-1)$ needs the factorisation; anybody who cannot factor $n$ cannot find $d$.

So the entire security argument rests on a theorem whose proof is thirty-two strings of beads sorted into eight piles. That is not a rhetorical flourish — the necklace argument, generalised by Euler’s count of coprime residues, is the theorem being invoked, and no deeper fact has been used anywhere in the scheme.

Counting the necklaces themselves #

The theorem drops out of the count as a by-product; the count itself is worth having, and asking for it in general leads somewhere the theorem does not.

How many distinct necklaces of $n$ beads in $a$ colours are there, for $n$ not prime? Now the orbits have different sizes — a string with period $d$ dividing $n$ has an orbit of size $d$ — so the strings cannot simply be divided by $n$. Sorting the strings by their exact period and counting each class gives

$$\text{necklaces} = \frac{1}{n}\sum_{d \mid n} \varphi(d)\, a^{n/d},$$

with $\varphi$ Euler’s totient. For $n$ prime the sum has two terms and collapses to $(a^p - a)/p + a$, which is the count above.

That formula is Burnside’s lemma applied to the rotation group, and it is the general form of the argument this essay makes in its special case: count the strings fixed by each rotation, average over the rotations, and the answer is the number of orbits. The necklace count is the standard first example of Pólya’s enumeration theory, which counts coloured objects up to symmetry and is the tool behind such questions as how many distinct dice faces, chemical isomers or tilings of a board exist.

So a proof of a theorem about remainders is also the first case of a general counting method, and the reason both exist is that dividing by a symmetry group is the same operation whether the aim is a count or a divisibility.

What the theorem is actually used for #

Fermat’s little theorem is the basis of essentially every practical test for primality, and its use has an unusual logical shape.

If $n$ is prime, $a^{n-1} \equiv 1 \pmod n$ for every $a$ coprime to $n$. Turning that around: if $a^{n-1} \not\equiv 1$ for some $a$, then $n$ is definitely composite. The computation takes a few hundred modular multiplications by repeated squaring, whatever the size of $n$, and it produces a certificate of compositeness without producing a single factor.

That asymmetry — proving a number composite while learning nothing about its factors — is what makes modern cryptography possible. Generating a thousand-digit prime means testing candidates until one passes, and the test never factors anything. The sieve, which is the only other way to establish primality, is hopeless at that size.

The converse fails, and it fails in an interesting way. Some composite numbers pass the test for a particular base — $341 = 11 \times 31$ satisfies $2^{340} \equiv 1 \pmod{341}$ — and are called pseudoprimes to that base. Most are caught by trying another base. The Carmichael numbers, of which $561$ is the smallest, pass for every base coprime to them, and there are infinitely many; they are the reason the naive test is not sufficient and the Miller–Rabin refinement exists.

Miller–Rabin patches the leak with one extra observation, and the observation is again about what a prime modulus permits. If $p$ is prime, the only square roots of $1$ modulo $p$ are $\pm 1$ — because $x^2 - 1 = (x-1)(x+1)$ and a prime dividing a product divides a factor. So while computing $a^{n-1}$ by repeated squaring, watch the intermediate values: if a square root of $1$ turns up that is neither $1$ nor $-1$, the modulus is composite, and it is composite even if the final answer comes out right. Carmichael numbers cannot survive that, and each round has at most a one-in-four chance of being fooled by any composite, so forty rounds leave an error probability far below the chance of the hardware being wrong.

Note what that costs and what it does not. The test is probabilistic, it never produces a factor, and a number that passes is called a probable prime — deliberately, because the test proves compositeness and only makes primality overwhelmingly likely. Deterministic polynomial-time primality testing exists, since the AKS algorithm of 2002, and is slower in practice than doing the probabilistic test forty times.

What the picture cannot show #

The figures draw every string, so they are limited to what can be drawn: five beads in two colours is thirty-two strings, and seven beads in three colours is two thousand one hundred and eighty-seven.

That is not a presentational limit but a structural one. The theorem is applied to $n$ of a thousand digits, where the number of strings is a number with $10^{1000}$ digits, and no counting argument is being performed — the modular exponentiation is. The picture explains why the theorem is true and gives no hint that it could be computed with.

There is a subtler gap. The figures show the orbits of a particular small case and the theorem quantifies over all $a$ and all primes $p$. What a figure can do is make the mechanism visible — a class has $p$ members unless the string is constant — and the generalisation from that to all cases is done in the prose, as it is everywhere in this collection. The drawing is a proof of the mechanism and an illustration of the theorem, and the distinction between those is worth keeping.

One more thing is deliberately not drawn. A necklace, as an object, can be turned over as well as rotated, and reflections would merge some of the classes in the figures — the strings 10110 and 01101 are reflections and sit in different rotation classes here. The figures show the rotation classes only, because reflection is not what the theorem counts: including it would change the orbit sizes, break the equal division, and destroy the proof. A picture of beads on a ring invites the reader to pick it up and flip it, and the argument requires that nobody does.

That is a small illustration of a general hazard in figure-first work. A drawing carries connotations that the mathematics has not agreed to, and the more physical the drawing the more it carries. The safest defence is to say which operations are in play, which this caption now does.

Fermat, and the letter #

Fermat stated the theorem in a letter to Frénicle de Bessy in October 1640, added that he would send the proof if it were not too long, and did not send it. That is entirely characteristic: of the many results he announced, he wrote out one complete proof in his life.

Euler published the first proof in 1736, using induction on $a$ and the binomial theorem — the key step being that the binomial coefficients $\binom{p}{k}$ for $0 < k < p$ are all divisible by $p$, which is visible in Pascal’s triangle mod $p$ as a row of blanks. Euler’s proof is essentially the necklace argument with the necklaces replaced by algebra, since the binomial coefficient counts the strings with $k$ beads of one colour and the divisibility is the same orbit count.

The necklace proof itself is much later — it is usually credited to Julius Petersen in 1872 — and its arrival is a good illustration of a pattern. A theorem gets an algebraic proof first, because algebra is what the people who state theorems are holding; the combinatorial proof, which explains rather than verifies, tends to arrive a century afterwards when somebody asks what the algebra was counting.

The same delay shows up throughout this collection. The dissection proof of Pythagoras is older than the algebra, but the bijection behind Catalan numbers, the necklace count here, and the involution behind the two-squares theorem all arrived long after the results they explain. A combinatorial proof is harder to find and easier to understand, which is a poor trade for the person doing the finding and an excellent one for everybody afterwards.

Where the ladder goes next #

The necklaces made one theorem about a prime modulus visible. The natural next question is what happens with two moduli at once, which is the Chinese remainder theorem — and its picture is a grid rather than a ring, with the same property that a walk fills it exactly when a coprimality condition holds.

Further along, the multiplicative structure this essay touched — orders, and the fact that they divide $p-1$ — is the beginning of the question of which residues are squares, and that question’s answer is quadratic reciprocity, which is again a count of one collection in two directions.