Wieferich prime

Wieferich prime

Named after	Arthur Wieferich
Publication year	1909
Author of publication	Wieferich, A.
Number of known terms	2
Subsequence of	Crandall numbers Wieferich numbers near-Wieferich primes
First terms	1093, 3511
Largest known term	3511
OEIS index	A001220

In number theory, a Wieferich prime is a prime number p such that p² divides 2^p − 1 − 1, therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2^p − 1 − 1. Wieferich primes were first described by Arthur Wieferich in 1909 in works pertaining to Fermat's last theorem, at which time both of Fermat's theorems were already well known to mathematicians.

Despite a number of extensive searches, the only known Wieferich primes to date are 1093 and 3511 (sequence A001220 in OEIS).

Explanation of the Wieferich property

The stronger version of Fermat's little theorem which a Wieferich prime satisfies is usually expressed as a congruence relation, namely the congruence 2^{p − 1} ≡ 1 (mod p²). From the definition of the congruence relation on integers it follows that this property is equivalent to the definition given at the beginning. Thus if a prime p satisfies this congruence, this prime divides the Fermat quotient $\frac{2^{p-1}-1}{p}$. The following are two illustrative examples using the primes 11 and 1093:

For 11 we get $\frac{2^{10}-1}{11}$ which is 93 and leaves a remainder of 5 after division by 11, hence 11 is not a Wieferich prime. For 1093 we get $\frac{2^{1092}-1}{1093}$ or 530585362....3096656895 (320 intermediate digits omitted for clarity), which leaves a remainder of 0 after division by 1093 and thus 1093 is a Wieferich prime.

Properties

Connection with Fermat's last theorem

The following theorem connecting Wieferich primes and Fermat's last theorem was proven by Wieferich in 1909:

Let p be prime, and let x, y, z be integers such that x^p + y^p + z^p = 0. Furthermore, assume that p does not divide the product xyz. Then p is a Wieferich prime.

The above case (where p does not divide any of x, y or z) is commonly known as the first case of Fermat's Last Theorem (FLTI) and we say that FLTI fails for a prime p, if solutions to the Fermat equation exist for that p, otherwise FLTI holds for p. In 1910, Mirimanoff expanded the theorem by showing that, if the preconditions of the theorem hold true for some prime p, then p² must also divide 3^p − 1 − 1. Morishima further proved that p² must actually divide m^p − 1 − 1 for every prime m ≤ 31. Granville and Monagan extended the proof to all m ≤ 89.

Connection with the abc conjecture

A non-Wieferich prime is a prime p satisfying 2^p − 1 ≢ 1 (mod p²). J. H. Silverman showed in 1988 that if the abc conjecture holds, then there exist infinitely many non-Wieferich primes. Numerical evidence suggests that very few of the prime numbers in a given interval are Wieferich primes. A proof of the abc conjecture would not automatically prove that there are only finitely many Wieferich primes, since the set of Wieferich primes and the set of non-Wieferich primes could possibly both be infinite and the finiteness or infiniteness of the set of Wieferich primes would have to be proven separately.

Connection with Mersenne and Fermat primes

It is known that the nth Mersenne number M_n = 2ⁿ − 1 is prime only if n is prime. Fermat's little theorem implies that if p > 2 is prime, then M_p−1 (= 2^p − 1 − 1) is always divisible by p. Since Mersenne numbers of prime indices M_p and M_q are co-prime,

A prime divisor p of M_q, where q is prime, is a Wieferich prime if and only if p² divides M_q.

Thus, a Mersenne prime cannot also be a Wieferich prime. A notable open problem is to determine whether or not all Mersenne numbers of prime index are square-free. If a Mersenne number M_q is not square-free, i.e., there exists a prime p for which p² divides M_q, then p is a Wieferich prime. Therefore, if there are only finitely many Wieferich primes, then there will be at most finitely many Mersenne numbers that are not square-free.

Similarly, if p is prime and p² divides some Fermat number F_n = 2²ⁿ + 1, then p must be a Wieferich prime.

Connection with other equations

Scott and Styer showed that if p is a Wieferich prime greater than 10¹⁵, then the Diophantine equation p^x−2^y=p^u−2^v has solutions in p, x, y, u, v with x≠u. They were later able to extend this result to other equations.

Binary periodicity of p-1

Johnson observed that the two known Wieferich primes are one greater than numbers with periodic binary expansions (1092 = 010001000100₂; 3510 = 110110110110₂). The Wieferich@Home project searches for Wieferich primes by testing numbers that are one greater than a number with a periodic binary expansion, but up to a "bit pseudo-length" of 3500 of the tested binary numbers generated by combination of bit strings with a bit length of up to 24 it has not found a new Wieferich prime.

Equivalent congruences

Wieferich primes can be defined by other congruences equivalent to the one usually used. If p is a Wieferich prime, we can multiply both sides of the congruence 2^p-1 ≡ 1 (mod p²) with 2 to get 2^p ≡ 2 (mod p²). Thus a Wieferich prime satisfies 2^p2 ≡ 2 (mod p²), since it must satisfy 2^kp ≡ 2 (mod p²) for all integers k ≥ 1.

History and search status

Unsolved problems in mathematics

Are there any Wieferich primes other than 1093 and 3511?

In 1902 W. F. Meyer proved a theorem about solutions of the congruence a^{p − 1} ≡ 1 (mod p^r). Later in that decade Arthur Wieferich showed specifically that if the First Case of Fermat's Last Theorem has solutions for an odd prime exponent, then that prime must satisfy that congruence for a = 2 and r = 2. In other words, if there exist solutions to x^p + y^p + z^p = 0 in integers x, y, z and p an odd prime with p ∤ xyz, then p satisfies 2^{p − 1} ≡ 1 (mod p²). In 1913, Bachmann examined the residues of $\frac{2^{p-1}-1}{p}\,\bmod\,p$. He asked the question when this residue vanishes and tried to find expressions for answering this question.

The prime 1093 was found to be a Wieferich prime by W. Meissner in 1913 by discovering the congruence 2³⁶⁴ ≡ 1 (mod 1093²) and confirmed to be the only such prime below 2000. The prime 3511 was found to be a Wieferich prime by N. G. W. H. Beeger in 1922. In 1960, Kravitz doubled a previous record set by Fröberg and in 1961 Riesel extended the search to 500000 with the aid of BESK. Around 1980, Lehmer was able to reach the search limit of 6×10⁹. This limit was extended to over 2.5×10¹⁵ in 2006, finally reaching 3×10¹⁵. It is now known, that if any other Wieferich primes exist, they must be greater than 6.7×10¹⁵. The search for new Wieferich primes is currently performed by the distributed computing project Wieferich@Home. Another search is performed by the PrimeGrid project. PrimeGrid has extended the search limit to 11×10¹⁵ and continues.

It has been conjectured that only finitely many Wieferich primes exist. It has also been conjectured (as for Wilson primes) that infinitely many Wieferich primes exist, and that the number of Wieferich primes below x is approximately log log x, which is a heuristic result that follows from the plausible assumption that for a prime p, the (p − 1)-th degree roots of unity modulo p² are uniformly distributed in the multiplicative group of integers modulo p².

Generalizations

Near-Wieferich primes

A prime p satisfying the congruence 2^(p−1)/2 ≡ ±1 + Ap (mod p²) with small |A| is commonly called a near-Wieferich prime (sequence A195988 in OEIS). Near-Wieferich primes with A = 0 represent Wieferich primes. Recent searches, in addition to their primary search for Wieferich primes, also tried to find near-Wieferich primes. The following table lists all near-Wieferich primes with |A| ≤ 10 in the interval [1×10⁹, 3×10¹⁵]. This search bound was reached in 2006 in a search effort by P. Carlisle, R. Crandall and M. Rodenkirch.

p	1 or −1	A
3520624567	+1	−6
46262476201	+1	+5
47004625957	−1	+1
58481216789	−1	+5
76843523891	−1	+1
1180032105761	+1	−6
12456646902457	+1	+2
134257821895921	+1	+10
339258218134349	−1	+2
2276306935816523	−1	−3

Dorais and Klyve used a different definition of a near-Wieferich prime, defining it as a prime p with small value of $\left|\frac{\omega(p)}{p}\right|$ where $\omega(p)=\frac{2^{p-1}-1}{p}\,\bmod\,p$ is the Fermat quotient of p modulo p (the modulo operation here gives the residue with the smallest absolute value). The following table lists all primes p ≤ 6.7 × 10¹⁵ with $\left|\frac{\omega(p)}p\right|\leq 10^{-14}$.

p	$\omega(p)$	$\left|\frac{\omega(p)}{p}\right|\times 10^{14}$
1093	0	0
3511	0	0
2276306935816523	+6	0.264
3167939147662997	−17	0.537
3723113065138349	−36	0.967
5131427559624857	−36	0.702
5294488110626977	−31	0.586
6517506365514181	+58	0.890

Base-a Wieferich primes

Main article: Fermat quotient

A Wieferich prime base a is a prime p that satisfies

a^p − 1 ≡ 1 (mod p²).

Such a prime cannot divide a, since then it would also divide 1.

Wieferich pairs

Main article: Wieferich pair

A Wieferich pair is a pair of primes p and q that satisfy

p^{q − 1} ≡ 1 (mod q²) and q^{p − 1} ≡ 1 (mod p²)

so that a Wieferich prime p ≡ 1 (mod 4) will form such a pair (p, 2): the only known instance in this case is p = 1093. There are 6 known Wieferich pairs.

Wieferich numbers

A Wieferich number is an odd integer w ≥ 3 satisfying the congruence 2^φ(w) ≡ 1 (mod w²). If Wieferich number w is prime, then it is a Wieferich prime. The first few Wieferich numbers are:

1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, … (sequence A077816 in OEIS)

It can be shown that if there are only finitely many Wieferich primes, then there are only finitely many Wieferich numbers. In particular, if the only Wieferich primes are 1093 and 3511, then there exist exactly 104 Wieferich numbers, which matches the number of Wieferich numbers currently known.

See also

• Wall–Sun–Sun prime - a hypothetical type of prime number defined in the study of Fermat's last theorem (FLT)
• Wolstenholme prime - another type of prime number which in the broadest sense also resulted from the study of FLT
• PrimeGrid

Further reading

• Haussner, R. (1926), "Über die Kongruenzen 2^p-1-1 ≡ 0 (mod p²) für die Primzahlen p=1093 und 3511", Archiv for Mathematik og Naturvidenskab 39 (5): 7, JFM 52.0141.06, DNB 363953469, http://jfm.sub.uni-goettingen.de/cgi-bin/jfmen/JFM/en/quick.html?first=1&maxdocs=20&type=html&an=JFM%2052.0141.06&format=complete 
• Haentzschel, E. (1925), "Über die Kongruenz 2¹⁰⁹² ≡ 1 (mod 1093²)", Jahresbericht der Deutschen Mathematiker-Vereinigung 34: 184, http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN37721857X_0034&DMDID=DMDLOG_0028 
• Bray, H. G.; Warren, L. J. (1967), "On the square-freeness of Fermat and Mersenne numbers", Pacific J. Math. 22 (3): 563–564, MR0220666, Zbl 0149.28204, http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pjm/1102992105 
• Silverman, J. H. (1988), "Wieferich's criterion and the abc-conjecture", Journal of Number Theory 30 (2): 226–237, doi:10.1016/0022-314X(88)90019-4 
• Ribenboim, P. (1979), Thirteen lectures on Fermat's Last Theorem, Springer-Verlag, pp. 139, 151, ISBN 0-387-90432-8 
• Guy, Richard K. (2004), Unsolved Problems in Number Theory (3rd ed.), Springer Verlag, p. 14, ISBN 0387208607 
• Garza, G.; Young, J. (2004), "Wieferich Primes and Period Lengths for the Expansions of Fractions", Math. Mag. 77 (4): 314–319, doi:10.2307/3219294, JSTOR 3219294 
• Crandall, R. E.; Pomerance, C. (2005), Prime numbers: a computational perspective, Springer Science+Business Media, Inc., pp. 31–32, ISBN 0-387-25282-7, http://books.google.com/?id=RbEz-_D7sAUC&pg=PA31&dq=wieferich+prime#v=onepage&q=wieferich%20prime&f=false 
• Ribenboim, P. (1996), The new book of prime number records, Springer-Verlag New York, Inc., pp. 333–346, ISBN 0-387-94457-5, http://books.google.com/?id=72eg8bFw40kC&pg=PA333&dq=wieferich+prime#v=onepage&q=wieferich%20prime&f=false 
• Broughan, K. (2006), "Relaxations of the ABC Conjecture using integer k'th roots", New Zealand J. Math. 35 (2): 121-136, http://www.math.waikato.ac.nz/~kab/papers/abc01.pdf 

External links

• Weisstein, Eric W., "Wieferich prime" from MathWorld.
• Fermat-/Euler-quotients (a^p−1 − 1)/p^k with arbitrary k
• A note on the two known Wieferich primes