# Theorems on Wieferich Primes

By John Blythe Dobson (j.dobson@uwinnipeg.ca)

### Introduction

Fermat’s Little Theorem states that the Fermat quotient
*q*_{p}(*b*)*b*^{p − 1} − 1)/*p* is a whole number. A Wieferich prime is one where *q*_{p}(2)*p*, while a Mirimanoff prime in one where *q*_{p}(3)*p*. The search for such primes, however, began long before they acquired these names, and has now lasted the better part of two centuries [4]. Despite the searches having been extended to high limits, only two primes have ever been found which possess the Wieferich property, which may equivalently be written

2^{p − 1}− 1 ≡ 0 (modp^{2}).

This page will not attempt to cover computational results, nor the observed digital cyclicity of the two known Wieferich primes, which has already been covered in our page A note on the two known Wieferich Primes. Rather, it will survey known theoretical results on Wieferich primes which require only a knowledge of elementary Number Theory, with new results being added as they become available. No originality is claimed for this material, which it is hoped will be useful to students.

### Theorem 1 (Gallardo, 2010)

### A prime *q* = 2*p* + 1 with *p* prime and *p* ≡ 3 (mod 4) cannot be a Wieferich prime

We rewrite the proof of this interesting observation by Luis H. Gallardo [1] to avoid explicit references to group-theoretic principles. Gallardo offers two slightly different versions of the proof, and a third proof based on properties of Bernoulli numbers, which we do not reproduce.

A prime *p* such that 2*p* + 1 is also prime is known as a Sophie Germain prime. If *p* ≡ 3 (mod 4), then *q* = 2*p* + 1 ≡ 7 (mod 8), and by Euler’s criterion, a prime of the form ±1 (mod 8) has 2 as a quadratic residue; in other words,

2^{(q − 1)/2}− 1 ≡ 0 (modq).

Thus,

2^{p}− 1 ≡ 0 (modq),

so that, incidentally, *q* is a divisor of the Mersenne number M_{p} = 2^{p} − 1. Because the left-hand side has no algebraic divisor, *p* is the least exponent *x* for which ^{x} − 1*q*); i.e. *p* is the order of 2 modulo *q*. Since the order of 2 = *p*, the order of −2 = 2*p* = *q* − 1 = φ(*q*), where φ(·) is Euler’s totient function. Therefore, −2 is a primitive root of *q*.

An 1867 theoreom of Lebesgue [5] (see Appendix) states that if *a* is a primitive root of *q*, then so is its modular inverse *a*′ ≡ 1/*a* ≡ *a*^{φ(q)−1} ≡ *a*^{q−2}, and that at least one of *a* and *a*′ is a primitive root of *q*^{2}. In the present case, since −2 is a primitive root of *q*, it follows that −2 or its modular inverse −½ is a primitive root of *q*^{2}, i.e. the order of at least one of them modulo *q*^{2} is φ(*q*^{2}) = *p*(*p* − 1)

Now assume that *q* possesses the Wieferich property, i.e. that 2^{q − 1} ≡ 1 (mod *q*^{2}), implying that the order of 2 modulo *q*^{2} is *q* − 1. But then it would follow that

(−2)^{2p}≡ (−1)^{2p}·2^{2p}≡ 2^{2p}≡ 1 (modq^{2})

and

(−½)^{2p}≡ (−1)^{2p}/2^{2p}≡ 1 (modq^{2}),

so the orders of −2 and −½ would each be 2*p* < *p*(*p* − 1)*q* = 2*p* + 1 with *p* prime and *p* ≡ 3 (mod 4) cannot be a Wieferich prime.

## Appendix

### Lebesgue’s Theorem on primitive roots (1867)

In [5] Lebesgue states without proof the following theorem: If *a* is a primitive root of *q*, then so is its modular inverse *a*′, and furthermore at least one of *a* and *a*′ is a primitive root of *q*^{2}. The following proof is adapted from an elegant paper by Maxfield & Maxfield [6], where a far more general result is obtained.

If *a* > 1 belongs to the exponent *e* (mod *p*), then by definition 1 > *e* ≥ *p* − 1*a*, *a*′ < *p*, and for some integer *k*,

a^{e}= 1 +kp.

Now

a^{pe}= (1 +kp)^{p}= 1 +pkp+ …

(with further terms divisible byp^{3})

≡ 1 (modp^{2}),

So that if *x* is the exponent to which *a* belongs (mod *p*^{2}), *x* must divide *pe*. But also *a*^{x} ≡ 1 (mod *p*^{2}) implies *a*^{x} ≡ 1 (mod *p*), whence *e* divides *x*. Thus *x* equals *e* or *pe*. So if *a* is a primitive root of *p*, i.e. *e* = *p*)*p* − 1*x* = *p* − 1*x* = *p*(*p* − 1

If the latter, the proof is complete. Otherwise, *a*^{x} = *a*^{e} ≡ 1 (mod *p*^{2}), and for some integer *c*,

(a′) =a^{e − 1}+cp,

so that

(a′)^{e}= (a^{e − 1}+cp)^{e}≡ (a^{e})^{e − 1}+ea^{e − l}cp+ …

(with further terms divisible byp^{2})

≡ 1 +ea^{e − l}cp(modp^{2}).

In order that we should likewise have (*a*′)^{e} ≡ 1 (mod *p*^{2}), it would be necessary for *p* to divide *c*. In that case, we should have *a*·*a*′ ≡ *a*^{e} + *acp* ≡ 1 (mod *p*^{2}), which would imply *a*·*a*′ ≥ *p*^{2} + 1*a* and *a*′ are both < *p*, so this is impossible. Thus, by the argument above, the order of *a*′ can only be *p*(*p* − 1*p*^{2})*a* is not a primitive root of *p*^{2}, then *a*′ necessarily is.

Note that Lebesgue stated that “at least one of” *a*, *a*′ is a primitive root of *p*^{2}. Indeed they may both be; for example 2 and its inverse 3, which are primitive roots of 5, are also primitive roots of 25.

## References

1. Luis H. Gallardo, “On special Wieferich’s primes,” preprint at http://arxiv.org/abs/1002.3840.

2. W. Johnson, “On the nonvanishing of Fermat quotients (mod *p*),” *Journal für die Reine und Angewandte Mathematik* 292 (1977): 196-200. Available online at http://www-gdz.sub.uni-goettingen.de/cgi-bin/digbib.cgi?PPN243919689_0292.

3. Wells Johnson, “On the *p*-Divisibility of the Fermat Quotients,” *Mathematics of Computation* 32 (1978): 297-301.

4. J. Knauer and J. Richstein, “The continuing search for Wieferich primes,” *Mathematics of Computation* 74 (2005): 1559-1563.

5. V. A. Lebesgue, “Théorème sur les racines primitives,” *Comptes rendus hebdomadaires des séances de l’Académie des sciences* [Paris] 64 (1867): 1268–1269.

6. John Maxfield & Margaret Maxfield, “The existence of integers less than *p*
belonging to *ep*^{r−1} (mod *p*^{r}),” *Mathematics Magazine* 33 (1959–1960): 219–220.

7. A. Rotkiewicz, “Sur les nombres de Mersenne dépourvus de diviseurs carrés et sur les nombres naturels *n* tels que *n*^{2} | 2^{n} − 2,” *Matematički Većnik* / *Matematicki Vesnik* 2(17) (1965): 78–80. We first learned of this little-known paper through various writings of Paulo Ribenboim.

8. Le Roy J. Warren and Henry G. Bray, “On the Square Freeness of Fermat and Mersenne Numbers,” *Pacific Journal of Mathematics* 22 (1967): 563–4. Available online at http://projecteuclid.org/handle/euclid.pjm/1102992105.

First published 4 October 2014

With minor revisions through to 15 June 2015