The row that proves a prime

Necklaces that prove a theorem counted the strings of $p$ beads in $a$ colours. The constant strings stand alone; every other string lies on a ring of exactly $p$ rotations, because $p$ is prime and no rotation short of a full turn can carry a mixed string onto itself. So $p$ divides $a^p - a$, which is Fermat’s little theorem.

The theorem is a test for primality with a famous flaw. The exponent that is smaller than Euler’s met the Carmichael numbers — $561$, $1105$, $1729$ and infinitely many more — which pass it for every base they share no factor with, although they are composite. The count that proved the theorem cannot tell them from primes, because it counts all the strings at once and the numbers happen to come out right.

This essay counts more carefully. Fix not the colours but how many beads are black, and the same necklace argument gives a statement that no composite number can fake.

There are $\binom 73 = 35$ ways to choose three black beads out of seven places on a ring. Group them by rotation and there are five necklaces, each standing for exactly seven arrangements. Seven divides thirty-five, and the reason is the same as in Fermat’s theorem: a prime number of places admits no partial symmetry.

One necklace that repeats too soon #

For a composite number of beads, the argument can fail, and the failure is visible.

With six beads and two black, there are fifteen arrangements. Two of the necklaces are full rings of six. The third — two black beads directly opposite each other — comes back to itself after three steps, so its ring has only three arrangements. Fifteen is six plus six plus three, and six does not divide fifteen.

That is the general picture. The size of every necklace’s ring divides the number of beads, and the ring is short exactly when the necklace has a rotational symmetry — when its pattern repeats with some period that divides $n$. For a prime $n$ there is no such period except $1$, which only the all-black and all-white necklaces have. For a composite $n$, take $k$ to be its smallest prime factor $q$ and the necklace with $q$ black beads spaced evenly round the ring: it repeats after $n/q$ steps. That short ring is enough to spoil the divisibility, and a computation with the factor $q$ shows that $\binom nq$ is never a multiple of $n$.

A row that only a prime can fill #

So the necklaces with a fixed number of black beads give a characterisation, not just a necessary condition.

A number $n$ greater than one is prime exactly when it divides every entry $\binom nk$ with $0 < k < n$. The figure shows the rows of Pascal’s triangle from $2$ to $20$ with each middle entry marked by whether the row’s number divides it. The prime rows are filled from end to end; every composite row has a gap. Row $6$ has gaps at $k = 2$, $3$ and $4$ — the opposite-beads necklace at $2$ and $4$, and at $3$ the necklace of alternating colours, which repeats after two steps; row $9$ at $k = 3$ and $k = 6$; row $15$ at the multiples of $3$ and $5$. The pattern of the gaps is Pascal’s triangle read modulo the row’s factors, where Lucas’s theorem computes each entry’s remainder from the digits of $n$ and $k$ in the base of a prime.

The Carmichael numbers cannot hide here. $561 = 3 \times 11 \times 17$ passes Fermat’s test for every base prime to it, but its row of Pascal’s triangle has gaps — at $k = 3$, $11$ and $17$ among other places, where the evenly spaced necklaces repeat early. The test that counts all colours at once adds up the row in a way that makes the gaps cancel; the test that looks at each entry separately sees them.

Where the gaps fall #

Which entries of a composite row fail has an exact answer, and it is written in the digits of the numbers involved.

Ernst Kummer proved in 1852 that the power of a prime $q$ dividing $\binom nk$ is the number of carries that occur when $k$ and $n - k$ are added in base $q$ — the rule the carries decide the divisibility drew. So $\binom nk$ is a multiple of $n$ exactly when, for every prime power $q^e$ dividing $n$, adding $k$ and $n - k$ in base $q$ produces at least $e$ carries. For a prime $n = p$, adding $k$ and $p - k$ in base $p$ always carries once, since the last digits add up to $p$; that is the necklace argument in the language of digits.

For $561 = 3 \times 11 \times 17$ the rule has to be satisfied in three bases at once, and it fails often: counting shows that $114$ of the $560$ middle entries of row $561$ are not multiples of $561$, starting at $k = 3, 9, 11, 12, 17, 18$. Each is a place where some addition in base $3$, $11$ or $17$ goes through without a carry — which is the digit form of a necklace repeating early. The Carmichael number has one hundred and fourteen necklace classes that betray it, and Fermat’s test consults none of them individually.

How the total hides the gaps #

Fermat’s test is the sum of the row. Choosing each of the $n$ beads black or white, the $2^n - 2$ strings that are not constant are the necklaces with $1, 2, \dots, n - 1$ black beads, so

$$2^n - 2 = \binom n1 + \binom n2 + \cdots + \binom n{n-1}.$$

If every term is a multiple of $n$, so is the sum, and that is the necklace proof of Fermat’s theorem for the base $2$. A composite can make the sum a multiple of $n$ while leaving terms that are not. The number $341 = 11 \times 31$ does exactly that: $2^{341} - 2$ is a multiple of $341$, so $341$ passes Fermat’s test with the base $2$ — it is the smallest number that does so without being prime — while $38$ of the $340$ middle entries of its row — beginning at $k = 11, 22, 31, 33$ — are not multiples of $341$. Their remainders cancel in the total.

A test that sees only the sum cannot see the cancellation, and every pseudoprime is a row whose failures add up to nothing. The polynomial test refuses to add them up, and that is the whole of its advantage over Fermat’s.

The row as a polynomial #

The row of Pascal’s triangle is the list of coefficients of $(x + 1)^n$, and the characterisation can be written as a single identity. Saying that $n$ divides every middle coefficient is saying that

$$(x + 1)^n \equiv x^n + 1 \pmod n$$

as polynomials, with every coefficient reduced modulo $n$. More generally, for any $a$ sharing no factor with $n$,

$$(x + a)^n \equiv x^n + a \pmod n$$

holds exactly when $n$ is prime. Setting $x = 0$ gives $a^n \equiv a$, which is Fermat’s theorem; so the polynomial identity implies Fermat’s theorem and is strictly stronger, because a composite can make the constant term come out right while leaving other coefficients behind.

The number $91 = 7 \times 13$ is a pseudoprime to the base $3$: $3^{90} \equiv 1 \pmod{91}$, and Fermat’s test with that base is fooled. The polynomial $(x + 1)^{91}$ reduced modulo $91$ is not fooled at all. Eighteen of its middle coefficients are not multiples of $91$, one at each multiple of $7$ and each multiple of $13$ below $91$, and the identity fails in eighteen places at once. The polynomial form of Fermat’s theorem cannot be fooled, because it asks every necklace class separately rather than asking for their total.

The same fact as the freshman’s dream #

The identity $(x + y)^p \equiv x^p + y^p \pmod p$ — the “freshman’s dream”, since it is the mistake beginners make with ordinary numbers — is the necklace count once more, and its reach goes far beyond primality.

It says that raising to the $p$-th power is additive when arithmetic is done modulo a prime. That makes the map $x \mapsto x^p$ a symmetry of any number system built with arithmetic modulo $p$ — the Frobenius map — and the finite fields are organised around it. In the field with four elements squaring swaps the two elements that are not $0$ or $1$; in the plane of order $2^h$ the translation hyperovals of every power of x that draws a hyperoval are the graphs of powers of the Frobenius map, and they work because it is additive. A fact about necklaces with a prime number of beads is the reason a whole branch of algebra has a distinguished symmetry.

Too many coefficients, and how to cut them down #

As a practical test, the polynomial identity is useless as it stands. It has $n + 1$ coefficients, and for a number with a hundred digits $n$ is a hundred-digit number of coefficients — no better than trying every possible factor.

Manindra Agrawal, Neeraj Kayal and Nitin Saxena found in 2002 how to cut it down. Wrap the polynomial round: work modulo $x^r - 1$ as well as modulo $n$, so that $x^r$ is replaced by $1$, $x^{r+1}$ by $x$, and so on. Every polynomial then has only $r$ coefficients, and $(x + a)^n$ can be computed with about $\log n$ squarings of polynomials of that size. The identity still holds for every prime; the question is whether composites can now slip through, since wrapping loses information.

Their theorem is that they cannot, provided $r$ is chosen so that $n$ has a large order modulo $r$ — larger than $(\log_2 n)^2$ — and the identity is checked for enough values of $a$, up to about $\sqrt r \log n$. Then an $n$ that passes, is not a perfect power and has no factor below $r$ must be prime. Such an $r$ exists below about $(\log n)^5$, so the whole test takes a number of steps bounded by a power of the number of digits of $n$. The figure runs the wrapped test on three primes and the three smallest Carmichael numbers: with $r$ between $89$ and $137$, the primes pass and every Carmichael number fails, for the first value of $a$ tried.

Why the test asks first about perfect powers #

The wrapped test has a preliminary step that looks like a technicality and is not: before any polynomial is powered, it checks whether $n$ is a perfect power — a square, a cube, some $m^b$ with $b \ge 2$ — and declares $n$ composite if so.

The reason is in the shape of the proof. Its argument shows that if the wrapped identity holds for enough values of $a$, then $n$ has a prime factor $p$ for which a large collection of polynomials behave, modulo $p$, as if $n$ were a power of $p$; counting those polynomials in two ways then forces $n$ to be a power of $p$. The count cannot distinguish $p$ from $p^2$ or $p^3$, so the proof ends at “$n$ is a power of a prime”, and the perfect-power check removes the powers. Checking whether a number is a perfect power is quick — for each exponent $b$ up to $\log_2 n$, compute an integer $b$-th root by bisection and raise it back — and it closes the one gap the polynomial argument leaves.

The unwrapped identity has no such gap. $(x + 1)^9$ modulo $9$ keeps the coefficient $\binom 93 = 84$, which leaves $3$, and prime powers fail the full row test exactly as other composites do. The cost of wrapping is the loss of that information, and the perfect-power check is what buys it back. Two primes where Fermat holds twice met the same distinction between a prime and its square from the other side: the squares of primes are where Fermat’s congruence can hold more strongly than it has to.

What was new about it #

Fast primality tests existed long before 2002. The Miller–Rabin test, a strengthening of Fermat’s that checks square roots of one along the way, is fast and fooled by no composite for more than a quarter of bases, so forty random bases make an error astronomically unlikely. And an order that proves a prime showed that every prime has a short certificate anyone can check.

What neither supplies is a procedure that is fast, never wrong and needs no luck and no certificate. Miller–Rabin is fast and could in principle be wrong; made deterministic by trying every base up to a bound, it needs the generalised Riemann hypothesis to be sure the bound suffices. The polynomial test of Agrawal, Kayal and Saxena is unconditionally correct and deterministically fast, and its proof uses nothing deeper than finite fields and a counting argument about how many polynomials an impostor would have to satisfy. That it was found by a professor and two undergraduates, in a subject worked on for two thousand years, is part of why it was celebrated.

In practice it is not used. Its running time, even after improvements by Hendrik Lenstra and Carl Pomerance brought the exponent down to about the sixth power of the number of digits, is far slower than Miller–Rabin, and primes that need certifying are certified by elliptic-curve methods that produce short proofs. The polynomial test’s importance is that it settled a question — primality is decidable in polynomial time — not that it is how primes are found.

What the rings and rows cannot show #

The necklaces are drawn for seven and six beads. The claim that prime lengths admit no short rings is general and simple; the claim that every composite length has a short ring is proved in words, with the evenly-spaced necklace, and illustrated at six.

Pascal’s triangle is drawn to row twenty. The figure checks the characterisation for every row it draws; the characterisation for every row is the necklace argument above.

The wrapped test is run with parameters chosen as the theorem requires, on six numbers below two thousand, and with one value of $a$. The theorem’s guarantee needs many values of $a$ in general; that one sufficed for these Carmichael numbers is an observation about them, not a replacement for the theorem.

Still open: a wrapped test that needs one value of a #

The polynomial test is slow because it must try many values of $a$ and use a large $r$. A conjecture, going back to the work of Rajat Bhattacharjee and Prashant Pandey and stated in the paper of Agrawal, Kayal and Saxena, would remove both costs: if $r$ is a prime not dividing $n$, and $(x - 1)^n \equiv x^n - 1$ modulo $x^r - 1$ and $n$, then either $n$ is prime or $n^2 \equiv 1 \pmod r$. It has been checked by computer for all $n$ below a very large bound and every small $r$, and if true it would give a test with running time about the cube of the number of digits, faster than any proven deterministic test.

Lenstra and Pomerance gave a heuristic argument that counterexamples should exist, built from numbers with many prime factors of a special form, and none has been found. So the conjecture is supported by computation, opposed by a heuristic, and unproved — a small version of the relationship between Fermat’s test and the Carmichael numbers, one level up.

Counting each class, not the total #

The habit worth keeping is the refinement of the count.

Fermat’s theorem came from counting all the strings of $p$ beads at once and noticing that the total, minus the constant strings, was a multiple of $p$. A total can be right for the wrong reasons, and the Carmichael numbers are totals that are right for the wrong reasons. Counting the strings with each number of black beads separately — each entry of the row of Pascal’s triangle on its own — asks the same question $n - 1$ times, and a composite number cannot answer all of them correctly. A sum of counts can be fooled; the counts themselves cannot, and the polynomial identity is the device that keeps them apart.