Wieferich prime

Wieferich prime

Named after	Arthur Wieferich
Publication year	1909
Author of publication	Wieferich, A.
No. of known terms	2
Subsequence of	Crandall numbers Wieferich numbers Lucas-Wieferich primes 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.

Since then, connections between Wieferich primes and various other topics in mathematics have been discovered, including other types of numbers and primes, such as Mersenne and Fermat numbers, specific types of pseudoprimes and some types of numbers generalized from the original definition of a Wieferich prime. Over time, those connections discovered have extended to cover more properties of certain prime numbers as well as more general subjects such as number fields and the abc conjecture.

Despite a number of extensive searches, the only known Wieferich primes to date are 1093 and 3511 (sequence A001220 in the 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 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 ${\tfrac {2^{p-1}-1}{p}}$. The following are two illustrative examples using the primes 11 and 1093:

For p = 11, we get ${\tfrac {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 p = 1093, we get ${\tfrac {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.

History and search status

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 ${\tfrac {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 Waldemar Meissner in 1913 and confirmed to be the only such prime below 2000. He calculated the smallest residue of ${\tfrac {2^{t}-1}{p}}\,{\bmod {\,}}p$ for all primes p < 2000 and found this residue to be zero for t = 364 and p = 1093, thereby providing a counterexample to a conjecture by Grawe about the impossibility of the Wieferich congruence. E. Haentzschel later ordered verification of the correctness of Meissners congruence via only elementary calculations. Inspired by an earlier work of Euler, he simplified Meissners proof by showing that 1093² | (2¹⁸² + 1) and remarked that (2¹⁸² + 1) is a factor of (2³⁶⁴ − 1). It was also shown that it is possible to prove that 1093 is a Wieferich prime without using complex numbers contrary to the method used by Meissner, although Meissner himself hinted at that he was aware of a proof without complex values. The prime 3511 was first found to be a Wieferich prime by N. G. W. H. Beeger in 1922 and another proof of it being a Wieferich prime was published in 1965 by Guy. 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. In December 2011, another search was started by the PrimeGrid project. As of February 2013, PrimeGrid has extended the search limit to 1×10¹⁷ and continues.

It has 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².

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 FLTI is said to fail 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. Granville and Monagan further proved that p² must actually divide m^p − 1 − 1 for every prime m ≤ 89. Suzuki extended the proof to all primes m ≤ 113.

Let H_p be a set of pairs of integers with 1 as their greatest common divisor, p being prime to x, y and x + y, (x + y)^p-1 ≡ 1 (mod p²), (x + ξy) being the pth power of an ideal of K with ξ defined as cos 2π/p + i sin 2π/p. K = Q(ξ) is the field extension obtained by adjoining all polynomials in the algebraic number ξ to the field of rational numbers (such an extension is known as a number field or in this particular case, where ξ is a root of unity, a cyclotomic number field). From uniqueness of factorization of ideals in Q(ξ) it follows that if the first case of Fermat's last theorem has solutions x, y, z then p divides x+y+z and (x, y), (y, z) and (z, x) are elements of H_p. Granville and Monagan showed that (1, 1) ∈ H_p if and only if p is a Wieferich prime.

Connection with the abc conjecture and non-Wieferich primes

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. More precisely he showed that the abc conjecture implies the existence of a constant only depending on α such that the number of non-Wieferich primes to base α with p less than or equal to a variable X is greater than log(X) as X goes to infinity. Numerical evidence suggests that very few of the prime numbers in a given interval are Wieferich primes. The set of Wieferich primes and the set of non-Wieferich primes, sometimes denoted by W₂ and W₂^c respectively, are complementary sets, so if one of them is shown to be finite, the other one would necessarily have to be infinite, because both are proper subsets of the set of prime numbers. It was later shown that the existence of infinitely many non-Wieferich primes already follows from a weaker version of the abc conjecture, called the ABC-(k, ε) conjecture. Additionally, the existence of infinitely many non-Wieferich primes would also follow if there exist infinitely many square-free Mersenne numbers as well as if there exists a real number ξ such that the set {n ∈ N : λ(2ⁿ − 1) < 2 − ξ} is of density one, where the index of composition λ(n) of an integer n is defined as ${\tfrac {\log n}{\log \gamma (n)}}$ and $\gamma (n)=\prod _{p\mid n}p$, meaning $\gamma (n)$ gives the product of all prime factors of n.

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, that is, 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. Rotkiewicz showed that the converse is also true, that is, if there are infinitely many square-free Mersenne numbers, then there are infinitely many non-Wieferich primes.

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

For the primes 1093 and 3511 it was shown that neither of them is a factor of any Mersenne or Fermat number.

Connection with other equations

Scott and Styer showed that the equation p^x – 2^y = d has at most one solution in positive integers (x, y), unless when p⁴ | 2^{ord_p 2} – 1 if p ≢ 65 mod 192 or unconditionally when p² | 2^{ord_p 2} – 1, where ord_p 2 denotes the multiplicative order of 2 modulo p. They also showed that a solution to the equation ±a^x₁ ± 2^y₁ = ±a^x₂ ± 2^y₂ = c must be from a specific set of equations but that this does not hold, if a is a Wieferich prime greater than 1.25 x 10¹⁵.

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, one can multiply both sides of the congruence 2^p-1 ≡ 1 (mod p²) by 2 to get 2^p ≡ 2 (mod p²). Raising both sides of the congruence to the power p shows that a Wieferich prime also satisfies 2^p2 ≡2^p ≡ 2 (mod p²), and hence 2^pk ≡ 2 (mod p²) for all k ≥ 1. The converse is also true: 2^pk ≡ 2 (mod p²) for some k ≥ 1 implies that the multiplicative order of 2 modulo p² divides gcd(p^k-1,φ(p²))=p-1, that is, 2^p-1 ≡ 1 (mod p²) and thus p is a Wieferich prime.

Bolyai showed that if p and q are primes, a is a positive integer not divisible by p and q such that a^p-1 ≡ 1 (mod q), a^q-1 ≡ 1 (mod p), then a^pq-1 ≡ 1 (mod pq). Setting p = q leads to a^p2-1 ≡ 1 (mod p²). It was shown that a^p2-1 ≡ 1 (mod p²) if and only if a^p-1 ≡ 1 (mod p²).

Connection with pseudoprimes

It was observed that the two known Wieferich primes are the square factors of all non-square free base-2 Fermat pseudoprimes up to 25×10⁹. Later computations showed that the only repeated factors of the pseudoprimes up to 10¹² are 1093 and 3511. In addition, the following connection exists: Let n be a base 2 pseudoprime and p be a prime divisor of n. If ${\tfrac {2^{n-1}-1}{n}}\not \equiv 0{\pmod {p}}$, then also ${\tfrac {2^{p-1}-1}{p}}\not \equiv 0{\pmod {p}}$. Furthermore if p is a Wieferich prime, then p² is a Catalan pseudoprime.

Connection with directed graphs

For all primes up to 100000 L(pⁿ⁺¹) = L(pⁿ) only for two cases: L(1093²) = L(1093) = 364 and L(3511²) = L(3511) = 1755, where m is the modulus of the doubling diagram and L(m) gives the number of vertices in the cycle of 1. The term doubling diagram refers to the directed graph with 0 and the natural numbers less than m as vertices with arrows pointing from each vertex x to vertex 2x reduced modulo m. It was shown, that for all odd prime numbers either L(pⁿ⁺¹) = p × L(pⁿ) or L(pⁿ⁺¹) = L(pⁿ).

Properties related to number fields

It was shown that $\chi _{D_{0}}{\big (}p{\big )}=1$ and $\lambda \,\!_{p}{\big (}\mathbb {Q} {\big (}{\sqrt {D_{0}}}{\big )}{\big )}=1$ if and only if 2^p − 1 ≢ 1 (mod p²) where p is an odd prime and $D_{0}<0$ is the fundamental discriminant of the imaginary quadratic field $\mathbb {Q} {\big (}{\sqrt {1-p^{2}}}{\big )}$. Furthermore the following was shown: Let p be a Wieferich prime. If p ≡ 3 (mod 4), let $D_{0}<0$ be the fundamental discriminant of the imaginary quadratic field $\mathbb {Q} {\big (}{\sqrt {1-p}}{\big )}$ and if p ≡ 1 (mod 4), let $D_{0}<0$ be the fundamental discriminant of the imaginary quadratic field $\mathbb {Q} {\big (}{\sqrt {4-p}}{\big )}$. Then $\chi _{D_{0}}{\big (}p{\big )}=1$ and $\lambda \,\!_{p}{\big (}\mathbb {Q} {\big (}{\sqrt {D_{0}}}{\big )}{\big )}=1$ (χ and λ in this context denote Iwasawa invariants).

Furthermore the following result was obtained: Let q be an odd prime number, k and p are primes such that p = 2k + 1, k ≡ 3 (mod 4), p ≡ −1 (mod q), p ≢ −1 (mod q³) and the order of q modulo k is ${\tfrac {k-1}{2}}$. Assume that q divides h⁺, the class number of the real cyclotomic field $\mathbb {Q} {\big (}\zeta \,\!_{p}+\zeta \,\!_{p}^{-1}{\big )}$, the cyclotomic field obtained by adjoining the sum of a p-th root of unity and its reciprocal to the field of rational numbers. Then q is a Wieferich prime. This also holds if the conditions p ≡ −1 (mod q) and p ≢ −1 (mod q³) are replaced by p ≡ −3 (mod q) and p ≢ −3 (mod q³) as well as when the condition p ≡ −1 (mod q) is replaced by p ≡ −5 (mod q) (in which case q is a Wall−Sun−Sun prime) and the incongruence condition replaced by p ≢ −5 (mod q³).

Order of 2 modulo powers of Wieferich primes

1093 and 3511 are the only primes up to 4 x 10¹² satisfying ord_p² 2 = ord_p 2 and it is known that ord₁₀₉₃ 2 = 364 and ord₃₅₁₁ 2 = 1755.

H. S. Vandiver proved that 2^p-1 ≡ 1 (mod p³) if and only if $1+{\tfrac {1}{3}}+\dots +{\tfrac {1}{p-2}}\equiv 0{\pmod {p^{2}}}$.

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 the 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|{\tfrac {\omega (p)}{p}}\right|$ where $\omega (p)={\tfrac {2^{p-1}-1}{p}}\,{\bmod {\,}}p$ is the Fermat quotient of 2 with respect to 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|{\tfrac {\omega (p)}{p}}\right|\leq 10^{-14}$.

p	$\omega (p)$	$\left|{\tfrac {\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 7 known Wieferich pairs.

Wieferich numbers

A Wieferich number is an odd integer w ≥ 3 satisfying the congruence 2^φ(w) ≡ 1 (mod w²), where φ(·) denotes the Euler function. 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 the 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.

More generally, an integer w is a Wieferich number to base a, if a^φ(w) ≡ 1 (mod w²).

Another definition specifies a Wieferich number as positive odd integer q such that q and ${\tfrac {2^{m}-1}{q}}$ are not coprime, where m is the multiplicative order of 2 modulo q. The first of these numbers are:

21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, … (sequence A182297 in the OEIS)

As above, if Wieferich number q is prime, then it is a Wieferich prime.

Lucas-Wieferich primes

A Lucas-Wieferich prime associated with the pair of integers (P, Q) is a prime p such that U_p-ε(P, Q) ≡ 0 (mod p²), where U_n(P, Q) denotes the Lucas sequence of the first kind and ε equals the Legendre symbol of P² - 4Q modulo p. All Wieferich primes are Lucas-Wieferich primes associated with the pair (3, 2).

Wieferich places

Let K be a global field, i.e. a number field or a function field in one variable over a finite field and let E be an elliptic curve. If v is a non-archimedean place of norm q_v of K and a ∈ K, with v(a) = 0 then v(a^q_v-1-1) ≥ 1. v is called a Wieferich place for base a, if v(a^q_v-1-1) > 1, an elliptic Wieferich place for base P ∈ E, if N_vP ∈ E₂ and a strong elliptic Wieferich place for base P ∈ E if n_vP ∈ E₂, where n_v is the order of P modulo v and N_v gives the number of rational points (over the residue field of v) of the reduction of E at v.

See also

• Wolstenholme prime – another type of prime number which in the broadest sense also resulted from the study of FLT
• Table of congruences - lists other congruences satisfied by prime numbers

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 (in German), 39 (5): 7, JFM 52.0141.06, DNB 363953469
• Haussner, R. (1927), "Über numerische Lösungen der Kongruenz u^p-1-1 ≡ 0 (mod p²)", Journal für die reine und angewandte Mathematik (Crelle's Journal). (in German), 1927 (156): 223–226, doi:10.1515/crll.1927.156.223
• 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 0-387-20860-7
• Crandall, R. E.; Pomerance, C. (2005), Prime numbers: a computational perspective (PDF), Springer Science+Business Media, Inc., pp. 31–32, ISBN 0-387-25282-7
• Ribenboim, P. (1996), The new book of prime number records, Springer-Verlag New York, Inc., pp. 333–346, ISBN 0-387-94457-5

External links

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