An order that proves a prime

Fermat’s little theorem says that if $p$ is prime, then $a^{p-1} \equiv 1 \pmod p$ for every $a$ not divisible by $p$. As a test for primality it is one-sided. A number that fails it is certainly composite. A number that passes may be prime, or may be one of the composites that pass for every base — the Carmichael numbers, of which 561 is the first. Passing the test is evidence and not proof.

There is a version of the test that proves. Instead of asking whether $a^{n-1}$ is 1, ask whether it is 1 for the first time at the exponent $n - 1$: whether the powers of $a$ cycle through $n - 1$ different values before returning. That stronger condition cannot be met by a composite, and meeting it is a proof.

The converse that works #

The order of $a$ modulo $n$ is the smallest positive exponent $k$ with $a^k \equiv 1$. The powers $a, a^2, \ldots, a^k$ are then all different, since a repeat would give a smaller exponent returning to 1, and all of them are coprime to $n$. So if $a$ has order $n - 1$, there are at least $n - 1$ numbers below $n$ coprime to it — which means every number from 1 to $n - 1$ is coprime to $n$, and $n$ is prime.

That is the converse of Fermat’s theorem that holds, due to Édouard Lucas in 1876 and refined by Derrick Lehmer in 1927. It asks for more than Fermat’s condition: not just that $a^{n-1}$ is 1, but that $a$ has no smaller exponent that works. And checking that does not require trying every smaller exponent. The order of $a$ divides $n - 1$, so if it is smaller than $n - 1$ it divides $(n-1)/q$ for some prime $q$ dividing $n - 1$. It suffices to check that $a^{(n-1)/q} \not\equiv 1$ for each prime factor $q$ of $n - 1$.

For 97, the number $96 = 2^5 \times 3$ has two prime factors, so two checks are needed: $5^{48}$ and $5^{32}$ modulo 97. The first is 96, the second 35, neither is 1, and $5^{96}$ is 1. So 5 has order 96, and 97 is prime. Two modular powers and a factorisation of 96 prove it. A number whose powers cycle through every nonzero residue is a primitive root, and the test is the statement that a primitive root can exist only modulo a prime — or a small number of prime-power relatives, none of which reaches $n - 1$.

The other direction is the one that makes the test complete: every prime has a primitive root, so the certificate always exists and the search for a base never fails. That is the theorem that the nonzero elements of a finite field are all powers of one of them, applied to the field of remainders modulo $p$. Without it Lucas’s test would be a sufficient condition that might sometimes be unavailable; with it, the test characterises the primes exactly.

Why a Carmichael number cannot pass #

The Carmichael numbers fool Fermat’s test because every base’s order divides $n - 1$ without being equal to it.

For 561 the largest order any base can have is Carmichael’s function $\lambda(561) = \operatorname{lcm}(2, 10, 16) = 80$. Every base raised to the 80th power is 1, so every base raised to the 560th is 1 — that is why Fermat’s test is fooled — but no base comes close to order 560. Lucas’s test asks exactly the question Fermat’s test skipped, and the answer is no for every base at once.

The gap is general. A composite $n$ has fewer than $n - 1$ numbers below it coprime to it, so no base can have $n - 1$ distinct powers, and the largest order is $\lambda(n)$, a divisor of that count of units and often a much smaller one — for a product of several primes it is the least common multiple of their individual orders, which shares a great deal among them.

The picture is the theorem in one plot. The primes lie on the line $n - 1$; every composite lies below it, most of them far below. The highest composite points are those just below the line, like $n = 4$ with order 2, and they never touch it. The figure computes the largest order two ways for the smaller $n$ — from the formula for $\lambda$, and by computing the order of every unit and taking the maximum — and requires them to agree.

The factors need proofs too #

Lucas’s test has a price: it needs the prime factors of $n - 1$. For 97 that is easy, since $96 = 2^5 \times 3$ is obviously factored. But “3 is prime” and “2 is prime” are claims, and for a large $n$ the prime factors of $n - 1$ are large primes whose primality is not obvious at all.

Trial division, the method of crossing out the composites, would settle small factors instantly and large ones never: a factor with fifty digits would need about $10^{25}$ divisions. The resolution is recursive: prove each prime factor prime in the same way. Each factor $q$ of $n - 1$ needs a base of order $q - 1$ and the prime factors of $q - 1$, each of which needs its own base and its own factors, until the factors are 2.

For 1009, one less is $1008 = 2^4 \times 3^2 \times 7$, and the base 11 has order 1008. The factor 7 needs its own certificate: $6 = 2 \times 3$, and the base 3 has order 6. The factor 3 needs one: $2$, with base 2. The tree has eight nodes and every node is checked by a handful of modular powers. Anyone handed the tree can verify it in minutes, and needs to trust nothing: every claim in it is checked by arithmetic, and every prime it relies on is proved further down.

Primes have short proofs #

Vaughan Pratt observed in 1975 that such trees are always small. At each node the prime factors of $q - 1$ multiply to less than $q$, so the total size of the factors shrinks as the tree descends, and a careful count shows the whole tree has at most about as many nodes as $n$ has binary digits, each node needing a few multiplications of numbers of that size. Every prime has a certificate whose length is a polynomial in its number of digits.

In the language of computational complexity, that places the primes in the class NP: the numbers for which a short proof of membership exists and can be checked quickly. The composites were already there — a factor is a short proof of compositeness — so Pratt’s certificates put primality in both NP and its complement. That was strong evidence that primality could be decided quickly without any certificate, and in 2002 Manindra Agrawal, Neeraj Kayal and Nitin Saxena proved that it can: the AKS algorithm decides primality in time polynomial in the number of digits, deterministically.

The certificate and the algorithm answer different questions. The algorithm decides; the certificate convinces. A prime found by a long computation can be published with its Pratt tree, and a reader with a pocket calculator and patience can check it, whereas checking an AKS computation means redoing it. The difference is the one between a proof and a verdict.

The certificates are also small in practice. A prime of a hundred digits typically has a tree of a few dozen nodes, most of them tiny primes near the leaves that are checked in an instant; the work is concentrated at the top, where the numbers are large, and each large node needs only one base and a few exponentiations. Printed out, the proof that a hundred-digit number is prime fits on a single sheet, which is shorter than the argument that most mathematical theorems of comparable age require.

Finding a witness is easy #

A certificate needs a base of order $p - 1$ at each node, and one might worry that such bases are rare. They are not.

The number of primitive roots modulo a prime $p$ is $\varphi(p - 1)$, the count of numbers below $p - 1$ coprime to it: if $g$ is one primitive root, the others are the powers $g^k$ with $k$ coprime to $p - 1$. So a random base is a witness with probability $\varphi(p-1)/(p-1)$, which for most primes is between a quarter and a half. The smallest values come when $p - 1$ has many small prime factors, as for 211, where $210 = 2 \times 3 \times 5 \times 7$ and only 48 of the 210 bases are witnesses. Even then, a handful of random tries finds one.

The average over primes, 0.378 here, tends to Artin’s constant, $0.3739558\ldots$, a product over all primes that measures the proportion of primes for which a fixed base such as 2 is a primitive root. So the hard part of a Lucas certificate is never the witness. It is the factorisation of $p - 1$, which for a general large prime is as hard as factoring. That is why the test is used in practice for primes of special forms, where $p - 1$ is factored by construction — Proth primes $k \cdot 2^m + 1$, for instance, and, through a close relative of the test, the Mersenne primes that give the even perfect numbers.

The Mersenne primes, and a test with no search at all #

For numbers of the form $2^m - 1$ the idea takes a sharper form. There, $n + 1$ rather than $n - 1$ is the fully factored number — it is a power of two — and a test due to Lucas, finished by Lehmer in 1930, works with the factorisation of $n + 1$ instead. Define $s_0 = 4$ and $s_{k+1} = s_k^2 - 2$; then $2^m - 1$, for odd prime $m$, is prime exactly when $s_{m-2}$ is divisible by it. No base has to be found and nothing has to be factored: the test is a fixed sequence of $m - 2$ squarings.

That is why the largest known primes are almost all Mersenne primes, with tens of millions of digits, and why the list of even perfect numbers grows only when a new Mersenne prime is found. It is also why the Mersenne prime $2^{19937} - 1$ gives its name to the Mersenne twister, a random-number generator whose period is that prime: the generator’s state cycles through every nonzero value exactly when a polynomial associated with it is primitive, which is Lucas’s condition in a polynomial disguise. The same logic that proves a number prime by exhibiting an element of full order proves a generator has full period by exhibiting a polynomial of full order, and in both cases the checks run over the prime factors of one number: $n - 1$ for the prime, and the period $2^{19937} - 1$ for the generator — which, being prime itself, has no smaller factors to check, and that is exactly why the designers chose it.

Only part of the factorisation #

Henry Pocklington showed in 1914 that the full factorisation of $n - 1$ is not needed. If $n - 1 = F \cdot R$ where $F$ is fully factored and larger than $\sqrt n$, and a base passes Lucas’s checks for the primes dividing $F$ only, then $n$ is prime. The reason is that every prime factor of $n$ would have to be one more than a multiple of $F$, and two such factors would multiply to more than $n$.

That turns an impossible requirement into a feasible one. Factoring a random 200-digit number is out of reach; finding a 100-digit factored part of it, by building the prime so that $n - 1$ has one, is not. The primes used in cryptography that need a proof of primality, rather than overwhelming probability, are made that way, and their certificates are Pocklington’s refinement of Lucas’s idea, a single step of Pratt’s tree with most of the branches pruned. The unfactored remainder $R$ never needs to be understood: it is enough that the factored part is large, which is a condition on what is known rather than on what is true.

What the figures cannot show #

The Lucas figures check two numbers, 97 and 561, and the λ figure checks every number to 200. The theorem that an element of order $n - 1$ exists exactly when $n$ is prime is the counting argument above, and the figures are instances of it. The Pratt tree is one certificate for one prime; that every prime has one of polynomial size is Pratt’s count of the tree’s nodes, which the figure illustrates at a size where the bound is loose.

The witness plot shows primes to 2,000 and an average that happens to be near Artin’s constant. That the average over all primes converges to the constant is a theorem; that a fixed base such as 2 is a primitive root for a proportion of primes equal to the constant is Artin’s conjecture, and it is not proved.

And none of the figures shows how long anything takes. The whole point of the certificate is that checking it is fast and finding it may not be; a figure that draws the finished tree conceals the factorisation effort at each node, which for large primes is the entire cost.

Still open: Artin’s conjecture #

Emil Artin conjectured in 1927 that every integer other than $-1$ and the perfect squares is a primitive root modulo infinitely many primes, and that for 2 the proportion of such primes is his constant. Christopher Hooley proved it in 1967 assuming the generalised Riemann hypothesis. Unconditionally, Roger Heath-Brown showed in 1986 that at least one of 2, 3 and 5 is a primitive root for infinitely many primes — without being able to say which.

So it is not known, without an unproved hypothesis, whether 2 is a primitive root modulo infinitely many primes: whether the base 2 works in Lucas’s test for infinitely many primes. The powers of 2 modulo a prime have been computed for every prime anyone could list, and 2 is a primitive root for about 37% of them, exactly as predicted. The obstacle is that proving it for infinitely many requires controlling how the primes distribute in arithmetic progressions of very large modulus, which is exactly what the Riemann hypothesis would supply and what nothing else yet does. The question matters for the tests only in principle — any small base that fails can be replaced by another — but it is a sharp illustration of how a statement that every computation confirms can depend on the deepest unproved conjecture in number theory.

A proof in a tree #

Fermat’s theorem tells a prime by what it does to powers, and on its own it can be fooled. Lucas’s converse cannot: an element whose powers visit all $n - 1$ nonzero residues before coming home exists only when $n$ is prime, because only then are there $n - 1$ residues to visit. Checking it needs the prime factors of $n - 1$, and proving those prime needs the same check again, down to 2.

The result is a certificate that fits on a page and needs no trust — eight nodes for 1009, a few dozen for a prime of a hundred digits. It was the first sign that primality is an easy property to prove as well as to test, and the algorithm that eventually made it easy to decide came twenty-seven years later. The necklaces of the first proof counted what the prime forces; the tree here records what the prime permits, and permission turns out to be the thing that can be written down.

Between the two directions lies the whole practical story of primes. Fermat’s direction gives the fast probabilistic tests that decide, in milliseconds, that a thousand-digit number is almost certainly prime; Lucas’s direction gives the certificates that make “almost certainly” into “certainly” when the factorisation of $n - 1$ can be arranged. And the primes that matter most in practice are chosen so that one of the two directions is easy.