Exploring Fermat's little theorem and Wieferich primes

One of the most important theorems of elementary number theory is Fermat's little theorem. It says that whenever an integer $a$ is not divisible by a prime $p$, the number $a^{p-1}-1$ is divisible by $p$. In terms of congruences we can write this statement as

\[ a^{p-1} -1 \equiv 0 \pmod{p} \]

An important philosophy for analyzing many problems in number theory is to first understand what happens modulo $p$, then modulo $p ^2$, then modulo $p ^3$ and so on. Taking this process to the limit gives the "$p$-adic" perspective on the problem.

Now apply this philosophy to Fermat's little theorem. You can study the number $a^{p-1} -1$ modulo $p ^2$ and so on, and this is already quite interesting. Here is some code that computes $2 ^{p-1} -1$ mod $p ^2$ for primes in the range $3$ to $100$. You can change the base $a=2$ to any other value and change the prime range too.

Can you in the above list find any prime $p$ such that the value of $2 ^{p-1} -1$ mod $p ^2$ is equal to zero? In the range $3$ to $100$, you cannot. But if you extend the prime range, you will find such a prime! How far do you need to go??

You may already suspect that primes with this property are quite rare, and in fact, we have special name for them - Wieferich prime (to base $2$). In general, a Wieferich prime to base $a$ is a prime $p$ such that

\[ a^{p-1} -1 \equiv 0 \pmod{p ^2} \]

Change the code above to base $a=3$. In this case, you will find a very small Wieferich prime immediately. But to find the next one, you have to go pretty far! (Hint: It is slightly larger than one million. See if you can find it.).

If you run the above code you get large and unwieldy remainders mod $p^2$. A small improvement is to check instead what's called the Fermat quotient

\[ \frac{a ^p -a}{p} \]

and print it's value mod $p$. Code here:

This Fermat quotient is of independent interest in the pursuit of $\mathbb{F}_1$-geometry, and you might recall seeing it in the paper of Manin with which we opened Episode 1 of the RH Saga.

See if you can find Wieferich primes for other bases $a$! If you do this for some different bases $a$, it will seem overwhelmingly plausible that there is (for any $a$) an infinite number of non-Wieferich primes. But in fact, this is not known! The main motivation for this post is that I wanted to show you a concrete prime number problem related to the abc conjecture, and here is such a problem. It is known that the abc conjecture would imply the existence of infinitely many non-Wieferich primes, for any given $a$.

What about the existence of infinitely many Wieferich primes? This is also not known, and as far as I know, there are no suggested routes to even begin attacking the problem. A probabilistic and non-rigorous argument suggests that the number of such primes up to $X$ should grow like $\log \log X$, i.e. going to infinity but at an extremely slow rate.

Recommended reading