Two primes where Fermat holds twice

Fermat’s little theorem says that $2^{p-1} - 1$ is divisible by $p$ for every odd prime $p$. For $p = 5$ the number is 15, divisible by 5 and not by 25. For $p = 7$ it is 63, divisible by 7 and not by 49. For $p = 11$ it is 1023, divisible by 11 and not by 121. It would be natural to guess that $p^2$ never divides it, and for every odd prime below 1093 the guess is right.

At $p = 1093$ it is wrong. Waldemar Meissner found in 1913 that $2^{1092} - 1$ is divisible by $1093^2$. N. G. W. H. Beeger found the second example, 3511, in 1922. A century of searching since, carried by 2022 to every prime below about $1.8 \times 10^{19}$, has found no third.

The primes where $p^2$ divides $2^{p-1} - 1$ are the Wieferich primes, after Arthur Wieferich, who showed in 1909 that they are exactly where a certain case of Fermat’s last theorem could fail. Between 1093 and 3511 and beyond, the picture is noise.

The quotient that Fermat’s theorem leaves #

Fermat’s theorem makes $(2^{p-1} - 1)/p$ a whole number, the Fermat quotient $q_p(2)$. Its remainder on division by $p$ is a number between 0 and $p - 1$, and $p^2$ divides $2^{p-1} - 1$ exactly when that remainder is 0.

Nothing in the theorem constrains the remainder. The figure plots it, divided by $p$ so that every prime gets a number between 0 and 1, for all 549 odd primes up to 4,000. The points fill the square evenly, with no drift, no preference for small values and no visible structure. The two that sit on the axis are the two Wieferich primes, and they look like accidents in a field of accidents.

That evenness is the basis of every estimate about Wieferich primes, and it is only a heuristic. If the remainder behaved like a random choice from $p$ possibilities, a given prime would be Wieferich with probability $1/p$. Nothing proves that it behaves that way; the figure is evidence that, for these primes, nothing obviously prevents it.

The quotient can be computed without the huge number $2^{p-1}$: compute $2^{p-1}$ modulo $p^2$ by repeated squaring, subtract 1, and divide by $p$. For $p$ up to a few thousand the numbers stay below $p^4$, well inside the range where ordinary arithmetic is exact. The figure checks, at every prime, that Fermat’s theorem holds before trusting the quotient.

Another base, other accidents #

Nothing about the phenomenon is specific to 2.

For base 3 the same scatter appears, and the first zero is at 11: $3^{10} - 1 = 59{,}048 = 121 \times 488$. The next is 1,006,003, far beyond the figure. Base 3 has its own Wieferich primes, unrelated to base 2’s, and they are just as sparse and just as patternless. The two scatters are not copies of each other either: at a given prime the quotients for base 2 and base 3 are unrelated numbers, and a prime that is ordinary for one base can be exceptional for another. What they share is the one thing Fermat’s theorem guarantees and nothing more.

Across six bases the search below 200,000 finds a scattering: 1093 and 3511 for base 2, 11 for base 3, 2, 20771 and 40487 for base 5, 5 for base 7, 3 and 487 for base 10, and 71 for base 11. There is no evident rule, no relation between the bases, and no tendency for the primes to cluster. The small ones are small only because small primes have larger chances: at $p = 5$ the chance is a fifth, and base 7 duly obliges.

What the extra divisibility does to an order #

The Wieferich condition has a cleaner description in terms of the order of 2, the length of the cycle its powers make.

Modulo $p$ the powers of 2 cycle with some period $d$ dividing $p - 1$. Modulo $p^2$ the period is a multiple of $d$ — reducing mod $p$ must still cycle — and divides $p(p - 1)$. It turns out to be either $d$ or $pd$, and it is $d$ exactly when $2^d \equiv 1 \pmod{p^2}$, which is exactly the Wieferich condition. So for every ordinary prime, the cycle modulo $p^2$ is $p$ times longer; for a Wieferich prime it is not longer at all.

That is a statement about lifting. Most facts that hold modulo $p$ can be lifted to $p^2$, $p^3$ and so on by a standard procedure — Hensel’s lemma — and the lift usually changes things by a factor of $p$ at each stage. The Wieferich primes are where the first lift of the powers of 2 is degenerate. For 1093 the order of 2 is 364 modulo $p$ and still 364 modulo $p^2$. For 3511 it is 1755 at both levels. For every other prime in the figure the cycle modulo $p^2$ is $p$ times the cycle modulo $p$, which is why the points line up on the diagonal so exactly: the ratio is not approximately $p$ but exactly $p$, and the figure computes it as such, by testing whether the shorter cycle already closes modulo $p^2$.

Fermat’s last theorem, a century early #

Wieferich’s interest in 1909 was not the primes themselves but what they excluded. Fermat’s last theorem says $x^p + y^p = z^p$ has no solutions in positive whole numbers for any odd prime $p$. Its “first case” is the claim for solutions in which $p$ divides none of $x$, $y$, $z$.

Wieferich proved that if the first case fails for a prime $p$, then $p$ is a Wieferich prime. In 1909 no Wieferich prime was known at all — 1093 was found four years later — so the theorem proved the first case for every prime that anyone checked, and the checks were cheap. Later work added base 3, base 5 and many more: a first-case counterexample at $p$ would force $p$ to be Wieferich for every base up to 89, and no prime is. So the first case was settled for enormous ranges of $p$ long before Andrew Wiles proved the whole theorem in 1995 by entirely different means.

The connection is a relic now, but it was the reason Wieferich primes were searched for so hard. Every prime cleared by the search was a prime for which a case of Fermat’s last theorem was known to hold, and the search was a way to approach the theorem one exponent at a time.

Relatives: Wilson primes and Wall–Sun–Sun primes #

The Wieferich primes are one of a family of “second-order” questions, each asking whether a congruence that holds modulo $p$ by some classical theorem happens to hold modulo $p^2$.

Wilson’s theorem says $(p - 1)! + 1$ is divisible by $p$ for every prime $p$ — the product of all the nonzero residues is $-1$, because every residue pairs with its inverse except $1$ and $-1$, a fact the arithmetic of a clock makes visible. The primes for which $p^2$ divides it are the Wilson primes, and only three are known: 5, 13 and 563, the last found in 1955, with searches since reaching beyond $2 \times 10^{13}$. The same one-in-$p$ heuristic applies, and gives the same slowly growing expectation.

For the Fibonacci numbers, $p$ divides $F_{p - (p/5)}$ for every prime other than 5, where the sign depends on $p$ modulo 5. A Wall–Sun–Sun prime is one where $p^2$ divides it, and none is known at all, in searches past $10^{17}$. Zhi-Hong Sun and Zhi-Wei Sun showed in 1992 that a first-case counterexample to Fermat’s last theorem at $p$ would make $p$ one of these as well — the same role Wieferich primes played, for a different sequence.

The pattern across the family is the same. A theorem supplies divisibility by $p$; the extra factor of $p$ is a coin with a one-in-$p$ chance of landing; the expected number is a sum of $1/p$ that barely grows; and the known examples are a handful of small primes where a coin with a large chance happened to land, followed by silence.

What the chance predicts #

If each odd prime $p$ is Wieferich independently with probability $1/p$, the expected number of Wieferich primes below $x$ is the sum of $1/p$ over odd primes up to $x$.

That sum grows without bound, but only like $\log \log x$ — the logarithm of the logarithm — as Mertens showed for the reciprocals of the primes. By $10^{19}$ it has reached about 3.6. The heuristic therefore predicts infinitely many Wieferich primes, and predicts that finding the next few requires searching ranges of exponentially exponential size: to expect one more beyond the current search, the bound has to be raised from $10^{19}$ to something like $10^{50}$.

So the drought is not evidence against the heuristic. Two found where 3.6 are expected is well within what a random count allows, and the flat stretch in the figure — no new prime for a factor of $10^{15}$ — is a stretch over which the expected count grows by only about one and a half. Small cases lie in number theory in both directions, and here the lie would be to read a century without a third example as a sign that there is none. A quantity growing like $\log\log x$ is almost invisible to computation: $\log\log x$ itself reaches 3 at about $5 \times 10^{8}$ and 4 only at about $5 \times 10^{23}$, so the whole of the searching done since 1913, from a thousand to $10^{19}$, has moved it from about 1.9 to about 3.8, and no feasible search will move it by more than a unit or so. The same slowness hides how rare sums of two squares become, whose density falls to nothing at a rate no computation could notice, and it is the rate at which the sieve of Eratosthenes fails to finish — the sum of $1/p$ that diverges, but only just.

What the heuristic cannot supply is a proof that Wieferich primes keep coming. Divergence of the expected count is a statement about a model in which the quotients are independent random numbers, and the actual quotients are determined by the arithmetic of powers of 2 in a way nobody has managed to control. The model says infinitely many; the mathematics says nothing.

Two bases at once #

A prime could be Wieferich for base 2 and base 3 simultaneously. Neither 1093 nor 3511 is Wieferich for base 3, and neither 11 nor 1,006,003 is Wieferich for base 2, and no prime is known that satisfies both conditions. On the heuristic, a prime satisfies both with probability $1/p^2$, and the sum of $1/p^2$ over all primes converges — to about 0.45 — so the heuristic predicts that such primes are finitely many, and probably none at all beyond the small range already searched.

That difference is instructive. A single condition with chance $1/p$ gives a divergent sum and infinitely many expected examples, however sparse; two independent conditions give a convergent sum and a finite expectation. The same arithmetic separates the Wieferich question from, say, primes where $p^3$ divides $2^{p-1} - 1$, of which the heuristic predicts only finitely many and none are known. Neither 1093 nor 3511 has a third factor: $2^{1092} - 1$ is divisible by $1093^2$ and not by $1093^3$. Where the heuristic says the expected count converges, the searches find nothing; where it says the count diverges, they find a handful. The heuristic has never been caught being wrong about which kind of question is which.

What the figures cannot show #

Every figure is a finite search, and the Wieferich primes are a question about all primes. The scatter of quotients looks random for primes to 4,000, and the heuristic depends on that randomness continuing; no one can prove it does, and there are other quotient-like quantities in number theory that look random for a long time and then reveal structure.

The expected-count curve is a heuristic plotted, not a theorem. It uses the known asymptotic for the sum of reciprocals of the primes, which is proved, and the assumption that each prime is Wieferich with chance $1/p$, which is not. The “found” staircase stops at the limit of the searches; beyond $1.8 \times 10^{19}$ nothing is known either way.

And the table of other bases shows the Wieferich primes below 200,000 only. Several bases have further known ones far beyond the table — base 3 at 1,006,003, base 7 at 491,531, base 10 at 56,598,313 — and some bases have none known at all. The quotient figures stop at 4,000 because beyond that the squares of the primes outgrow the exact arithmetic the figures use; the table of bases switches to arbitrarily large whole numbers to go further, and searches beyond it use the same method on much faster machines. None of them changes the picture, which is a scatter with nothing in it but chance.

Still open: more, or infinitely many, or infinitely many of the other kind #

It is not known whether there are infinitely many Wieferich primes. It is also not known whether there are infinitely many non-Wieferich primes — primes $p$ for which $p^2$ does not divide $2^{p-1} - 1$ — although every prime anyone has tested except two is one.

That second gap is the stranger. The non-Wieferich primes are, by every measure, almost all primes, and yet no proof shows there are infinitely many. Joseph Silverman proved in 1988 that there are infinitely many assuming the abc conjecture, a deep statement about the prime factors of $a$, $b$ and $a + b$. Without it the question is open. A property shared by all but two of the primes below $10^{19}$ cannot be shown to hold for infinitely many of them, which is a precise measure of how little is known about the digits of $2^{p-1}$ beyond what Fermat’s theorem says.

The abc conjecture itself was claimed proved by Shinichi Mochizuki in 2012, in a series of papers whose argument most specialists have not accepted, and whose status remains disputed. If a proof were accepted, the infinitude of non-Wieferich primes would follow immediately. Until then, the statement that almost every prime is not Wieferich — true of every prime below $10^{19}$ with two exceptions — is known only conditionally.

Twice, by accident #

Fermat’s theorem guarantees one factor of $p$ in $2^{p-1} - 1$. A second factor is an extra coincidence, a one-in-$p$ event if the leftover quotient is as random as it looks, and the searches have found it twice: at 1093, in 1913, and at 3511, in 1922. Every other prime to $10^{19}$ has the single factor and no more.

The numbers fit a random model that predicts infinitely many such primes, arriving at a rate so slow that a third may lie beyond any search that will ever be run. They also fit, as far as anyone can prove, a world in which there are only two. And the opposite statement — that infinitely many primes have only the one factor — is equally beyond proof. Between the theorem Fermat stated and the question it leaves, a single extra power of $p$ marks the edge of what number theory can say about $2^{p-1}$.

The necklaces that proved Fermat’s theorem counted strings of beads round a loop and found them falling into rings of $p$, which forced the one factor. No counting argument of that kind gives the second, and the Fermat quotient is what is left over when the counting stops — a residue that every known method sees as noise. That the noise has landed on zero twice, and that nobody can say whether it will again, is a fair summary of how the theorem that the exponent is smaller than Euler’s and the theorems around it end: with a count that is exact, and a remainder that is not understood.