[Up to Mathematics projects]

Theorems on Wieferich Primes

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

Although the author is employed by the University of Winnipeg, he has no affiliation with the Mathematics Department or with any other academic department.

Introduction

Fermat’s Little Theorem states that the Fermat quotient qp(b) = (bp − 1 − 1)/p is a whole number. A Wieferich prime is one where qp(2) is divisible by p, while a Mirimanoff prime in one where qp(3) is divisible by 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

2p − 1 − 1 ≡ 0 (mod p2).

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 = 2p + 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 2p + 1 is also prime is known as a Sophie Germain prime. If p ≡ 3 (mod 4), then q = 2p + 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 (mod q).

Thus,

2p − 1 ≡ 0 (mod q),

so that, incidentally, q is a divisor of the Mersenne number Mp = 2p − 1. Because the left-hand side has no algebraic divisor, p is the least exponent x for which 2x − 1 ≡ 0 (mod q); i.e. p is the order of 2 modulo q. Since the order of 2 = p, the order of −2 = 2p = 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/aaφ(q)−1aq−2, and that at least one of a and a′ is a primitive root of q2. 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 q2, i.e. the order of at least one of them modulo q2 is φ(q2) = p(p − 1).

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

(−2)2p ≡ (−1)2p·22p ≡ 22p ≡ 1 (mod q2)

and

(−½)2p ≡ (−1)2p/22p ≡ 1 (mod q2),

so the orders of −2 and −½ would each be 2p < p(p − 1), contradicting Lebesgue’s theorem. Thus, a prime q = 2p + 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 q2. 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 > ep − 1, and a, a′ < p, and for some integer k,

ae = 1 + kp.

Now

ape = (1 + kp)p = 1 + pkp + …
(with further terms divisible by p3)
≡ 1 (mod p2),

So that if x is the exponent to which a belongs (mod p2), x must divide pe. But also ax ≡ 1 (mod p2) implies ax ≡ 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, then either x = p − 1 or x = p(p − 1).

If the latter, the proof is complete. Otherwise, ax = ae ≡ 1 (mod p2), and for some integer c,

(a′) = ae − 1 + cp,

so that

(a′)e = (ae − 1 + cp)e ≡ (ae)e − 1 + eae − lcp + …
(with further terms divisible by p2)
≡ 1 + eae − lcp (mod p2).

In order that we should likewise have (a′)e ≡ 1 (mod p2), it would be necessary for p to divide c. In that case, we should have a·a′ ≡ ae + acp ≡ 1 (mod p2), which would imply a·a′ ≥ p2 + 1. But by definition 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) = φ(p2). In other words, if a is not a primitive root of p2, then a′ necessarily is.

Note that Lebesgue stated that “at least one of” a, a′ is a primitive root of p2. 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 epr−1 (mod pr),” 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 n2 | 2n − 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