Wieferich prime

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Wieferich prime
Named after Arthur Wieferich
Publication year 1909
Author of publication Wieferich, A.
Number of known terms 2
Subsequence of Crandall numbers[1]
Wieferich numbers[2]
Lucas-Wieferich primes[3]
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 p2 divides 2p − 1 − 1,[4] therefore connecting these primes with Fermat's little theorem, which states that every odd prime p divides 2p − 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.[5][6]

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.

As of October 2013, the only known Wieferich primes are 1093 and 3511 (sequence A001220 in OEIS).

Equivalent definitions[edit]

The stronger version of Fermat's little theorem, which a Wieferich prime satisfies, is usually expressed as a congruence relation 2p − 1 ≡ 1 (mod p2). 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 485439490310...852893958515 (302 intermediate digits omitted for clarity), which leaves a remainder of 0 after division by 1093 and thus 1093 is a Wieferich prime.

Wieferich primes can be defined by other equivalent congruences. If p is a Wieferich prime, one can multiply both sides of the congruence 2p-1 ≡ 1 (mod p2) by 2 to get 2p ≡ 2 (mod p2). Raising both sides of the congruence to the power p shows that a Wieferich prime also satisfies 2p2 ≡2p ≡ 2 (mod p2), and hence 2pk ≡ 2 (mod p2) for all k ≥ 1. The converse is also true: 2pk ≡ 2 (mod p2) for some k ≥ 1 implies that the multiplicative order of 2 modulo p2 divides gcd(pk-1,φ(p2))=p-1, that is, 2p-1 ≡ 1 (mod p2) and thus p is a Wieferich prime. This also implies that Wieferich primes can be defined as primes p such that the multiplicative orders of 2 modulo p and modulo p2 coincide: ordp2 2 = ordp 2, (By the way, ord10932 = 364, and ord35112 = 1755).

H. S. Vandiver proved that 2p-1 ≡ 1 (mod p3) if and only if 1 + \tfrac{1}{3} + \dots + \tfrac{1}{p-2} \equiv 0 \pmod{p^2}.[7]:187

History and search status[edit]

In 1902, W. F. Meyer proved a theorem about solutions of the congruence ap − 1 ≡ 1 (mod pr).[8]:930 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 xp + yp + zp = 0 in integers x, y, z and p an odd prime with p xyz, then p satisfies 2p − 1 ≡ 1 (mod p2). 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.[9]

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.[10] E. Haentzschel later ordered verification of the correctness of Meissners congruence via only elementary calculations.[11]:664 Inspired by an earlier work of Euler, he simplified Meissners proof by showing that 10932 | (2182 + 1) and remarked that (2182 + 1) is a factor of (2364 − 1).[12] 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,[13] although Meissner himself hinted at that he was aware of a proof without complex values.[10]:665

The prime 3511 was first found to be a Wieferich prime by N. G. W. H. Beeger in 1922[14] and another proof of it being a Wieferich prime was published in 1965 by Guy.[15] In 1960, Kravitz[16] doubled a previous record set by Fröberg[17] and in 1961 Riesel extended the search to 500000 with the aid of BESK.[18] Around 1980, Lehmer was able to reach the search limit of 6×109.[19] This limit was extended to over 2.5×1015 in 2006,[20] finally reaching 3×1015. It is now known, that if any other Wieferich primes exist, they must be greater than 6.7×1015.[21] 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.[22] As of October 2014, PrimeGrid has extended the search limit to over 3×1017 and continues.[23]

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 p2 are uniformly distributed in the multiplicative group of integers modulo p2.[24]

Properties[edit]

Connection with Fermat's last theorem[edit]

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

Let p be prime, and let x, y, z be integers such that xp + yp + zp = 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)[26][27] 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.[28] In 1910, Mirimanoff expanded[29] the theorem by showing that, if the preconditions of the theorem hold true for some prime p, then p2 must also divide 3p − 1 − 1. Granville and Monagan further proved that p2 must actually divide mp − 1 − 1 for every prime m ≤ 89.[30] Suzuki extended the proof to all primes m ≤ 113.[31]

Let Hp 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 p2), (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).[30]:332 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 Hp.[30]:333 Granville and Monagan showed that (1, 1) ∈ Hp if and only if p is a Wieferich prime.[30]:333

Connection with the abc conjecture and non-Wieferich primes[edit]

A non-Wieferich prime is a prime p satisfying 2p − 1 ≢ 1 (mod p2). J. H. Silverman showed in 1988 that if the abc conjecture holds, then there exist infinitely many non-Wieferich primes.[32] 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.[33]:227 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 W2 and W2c respectively,[34] 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.[35] Additionally, the existence of infinitely many non-Wieferich primes would also follow if there exist infinitely many square-free Mersenne numbers[36] as well as if there exists a real number ξ such that the set {nN : λ(2n − 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.[34]:4

Connection with Mersenne and Fermat primes[edit]

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

A prime divisor p of Mq, where q is prime, is a Wieferich prime if and only if p2 divides Mq.[37]

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 q is prime and the Mersenne number Mq is not square-free, that is, there exists a prime p for which p2 divides Mq, 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 with prime index that are not square-free. Rotkiewicz showed a related result: if there are infinitely many square-free Mersenne numbers, then there are infinitely many non-Wieferich primes.[38]

Similarly, if p is prime and p2 divides some Fermat number Fn = 22n + 1, then p must be a Wieferich prime.[39]

In fact, if and only if there exists a natural number n and a prime p that p2 divides \Phi_n(2) (where \Phi is Cyclotomic polynomial), then p is a Wieferich prime. For example, 10932 divides \Phi_{364}(2), 35112 divides \Phi_{1755}(2). Mersenne and Fermat numbers are just special situations of \Phi_n(2). Thus, if 1093 and 3511 are only two Wieferich primes, then all \Phi_n(2) are square-free except \Phi_{364}(2) and \Phi_{1755}(2) (In fact, when there exists a prime p which p2 divides some \Phi_n(2), then it is a Wieferich prime); and clearly, if \Phi_n(2) is a prime, then it cannot be Wieferich prime. (Notice any odd prime p divides only one \Phi_n(2) and n divides p-1, and if and only if the period length of 1/p in binary is n, then p divides \Phi_n(2). Besides, if and only if p is a Wieferich prime, then the period length of 1/p and 1/p2 are the same (in binary). Otherwise, this is p times than that.)

For the primes 1093 and 3511, it was shown that neither of them is a divisor of any Mersenne number with prime index nor a divisor of any Fermat number, because 364 and 1755 are neither prime nor powers of 2.[40]

Connection with other equations[edit]

Scott and Styer showed that the equation px – 2y = d has at most one solution in positive integers (x, y), unless when p4 | 2ordp 2 – 1 if p ≢ 65 (mod 192) or unconditionally when p2 | 2ordp 2 – 1, where ordp 2 denotes the multiplicative order of 2 modulo p.[41]:215, 217–218 They also showed that a solution to the equation ±ax1 ± 2y1 = ±ax2 ± 2y2 = 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 1015.[42]:258

Binary periodicity of p−1[edit]

Johnson observed[43] that the two known Wieferich primes are one greater than numbers with periodic binary expansions (1092 = 0100010001002=44416; 3510 = 1101101101102=66668). 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.[44]

Abundancy of p−1[edit]

It has been noted (sequence A239875 in OEIS) that the known Wieferich primes are one greater than mutually friendly numbers (the shared abundancy index being 112/39).

Connection with pseudoprimes[edit]

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×109.[45] Later computations showed that the only repeated factors of the pseudoprimes up to 1012 are 1093 and 3511.[46] 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}.[28]:378 Furthermore if p is a Wieferich prime, then p2 is a Catalan pseudoprime.[47]

Connection with directed graphs[edit]

For all primes up to 100000 L(pn+1) = L(pn) only for two cases: L(10932) = L(1093) = 364 and L(35112) = 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.[48]:74 It was shown, that for all odd prime numbers either L(pn+1) = p × L(pn) or L(pn+1) = L(pn).[48]:75

Properties related to number fields[edit]

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 2p − 1 ≢ 1 (mod p2) 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).[49]:27

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 q3) 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.[50]:55 This also holds if the conditions p ≡ −1 (mod q) and p ≢ −1 (mod q3) are replaced by p ≡ −3 (mod q) and p ≢ −3 (mod q3) 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 q3).[51]:376

Generalizations[edit]

Near-Wieferich primes[edit]

A prime p satisfying the congruence 2(p−1)/2 ≡ ±1 + Ap (mod p2) with small |A| is commonly called a near-Wieferich prime (sequence A195988 in OEIS).[24][52] 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.[21][53] The following table lists all near-Wieferich primes with |A| ≤ 10 in the interval [1×109, 3×1015].[54] This search bound was reached in 2006 in a search effort by P. Carlisle, R. Crandall and M. Rodenkirch.[20][55]

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

The sign +1 or -1 above can be easily predicted by Euler's criterion (and the second supplement to the law of quadratic reciprocity).

Dorais and Klyve[21] 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 × 1015 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

The two notions of nearness are related as follows. If 2^{(p-1)/2}\equiv \pm 1 + Ap \pmod{p^2}, then by squaring, clearly 2^{p-1}\equiv 1 \pm 2Ap \pmod{p^2}. So if A had been chosen with |A| small, then clearly |\pm 2A|=2|A| is also (quite) small, and an even number. However, when \omega(p) is odd above, the related A from before the last squaring was not "small". For example with p=3167939147662997, we have 2^{(p-1)/2}\equiv -1 - 1583969573831490p \pmod{p^2} which reads extremely non-near, but after squaring this is 2^{p-1}\equiv 1 - 17p \pmod{p^2} which is a near-Wieferich by the second definition.

Base-a Wieferich primes[edit]

Main article: Fermat quotient

A Wieferich prime base a is a prime p that satisfies

ap − 1 ≡ 1 (mod p2).[8]

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

It is conjectured that there are infinitely many Wieferich primes in every base a.

Bolyai showed that if p and q are primes, a is a positive integer not divisible by p and q such that ap-1 ≡ 1 (mod q), aq-1 ≡ 1 (mod p), then apq-1 ≡ 1 (mod pq). Setting p = q leads to ap2-1 ≡ 1 (mod p2).[56]:284 It was shown that ap2-1 ≡ 1 (mod p2) if and only if ap-1 ≡ 1 (mod p2).[56]:285–286

Known solutions of ap-1 ≡ 1 (mod p2) for small values of a are:[57]

a p (checked up to 5 × 1013) OEIS sequence
1 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All primes) A000040
2 1093, 3511 A001220
3 11, 1006003 A014127
4 1093, 3511
5 2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801 A123692
6 66161, 534851, 3152573 A212583
7 5, 491531 A123693
8 3, 1093, 3511
9 2, 11, 1006003
10 3, 487, 56598313 A045616
11 71
12 2693, 123653 A111027
13 2, 863, 1747591 A128667
14 29, 353, 7596952219 A234810
15 29131, 119327070011 A242741
16 1093, 3511
17 2, 3, 46021, 48947, 478225523351 A128668
18 5, 7, 37, 331, 33923, 1284043 A244260
19 3, 7, 13, 43, 137, 63061489 A090968
20 281, 46457, 9377747, 122959073 A242982
21 2
22 13, 673, 1595813, 492366587, 9809862296159
23 13, 2481757, 13703077, 15546404183, 2549536629329 A128669
24 5, 25633
25 2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801
26 3, 5, 71, 486999673, 6695256707
27 11, 1006003
28 3, 19, 23
29 2
30 7, 160541, 94727075783

For more information, see[58][59][60] and.[61]

The smallest solutions of np-1 ≡ 1 (mod p2) are

2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, 2693, 2, 29, 29131, 1093, 2, 5, 3, 281, 2, 13, 13, 5, 2, 3, 11, 3, 2, 7, 7, 5, 2, 46145917691, 3, 66161, 2, 17, 8039, 11, 2, 23, 5, 3, 2, 3, ... (The next term > 4.9×1013) (sequence A039951 in OEIS)

The smallest solutions > sqrt(n) of np-1 ≡ 1 (mod p2) are

2, 1093, 11, 1093, 20771, 66161, 5, 3, 11, 487, 71, 2693, 863, 29, 29131, 1093, 46021, 5, 7, 281, ... (The next term > 3.4×1013)

There are no known solutions of np-1 ≡ 1 (mod p2) for that n = 47, 72, 186, 187, 200, 203, 222, 231, 304, 311, 335, 347, 355, 435, 454, ..., and that there are small solutions but no known solutions > sqrt(n) of np-1 ≡ 1 (mod p2) for that n = 21, 29, 50, 61, 73, 82, 126, 132, 154, 188, 237, 301, 309, 327, 351, 357, 441, 458, 496, ...

It is a conjecture that there are infinity many solutions of np-1 ≡ 1 (mod p2) for every natural number n.

The bases b < p2 which p is a Wieferich prime are (for b > p2, the solutions are just shifted by k*p2 for k > 0), and there are p - 1 solutions < p2 of p and the set of the solutions congruent to p are {1, 2, 3, ..., p - 1}) (sequence A143548 in OEIS)

p values of b < p2
2 1
3 1, 8
5 1, 7, 18, 24
7 1, 18, 19, 30, 31, 48
11 1, 3, 9, 27, 40, 81, 94, 112, 118, 120
13 1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168
17 1, 38, 40, 65, 75, 110, 131, 134, 155, 158, 179, 214, 224, 249, 251, 288
19 1, 28, 54, 62, 68, 69, 99, 116, 127, 234, 245, 262, 292, 293, 299, 307, 333, 360
23 1, 28, 42, 63, 118, 130, 170, 177, 195, 255, 263, 266, 274, 334, 352, 359, 399, 411, 466, 487, 501, 528
29 1, 14, 41, 60, 63, 137, 190, 196, 221, 236, 267, 270, 374, 416, 425, 467, 571, 574, 605, 620, 645, 651, 704, 778, 781, 800, 827, 840

The least base b > 1 which prime(n) is a Wieferich prime are

5, 8, 7, 18, 3, 19, 38, 28, 28, 14, 115, 18, 51, 19, 53, 338, 53, 264, 143, 11, 306, 31, 99, 184, 53, 181, 43, 164, 96, 68, 38, 58, 19, 328, 313, 78, 226, 65, 253, 259, 532, 78, 176, 276, 143, 174, 165, 69, 330, 44, 33, 332, 94, 263, 48, 79, 171, 747, 731, 20, ... (sequence A039678 in OEIS)

Wieferich pairs[edit]

Main article: Wieferich pair

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

pq − 1 ≡ 1 (mod q2) and qp − 1 ≡ 1 (mod p2)

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 only 7 known Wieferich pairs.[62]

(2, 1093), (3, 1006003), (5, 1645333507), (5, 188748146801), (83, 4871), (911, 318917), and (2903, 18787) (sequences A124121, A124122 and A126432 in OEIS)

Wieferich numbers[edit]

A Wieferich number is an odd integer w ≥ 3 satisfying the congruence 2φ(w) ≡ 1 (mod w2), 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, 52665, 68859, 94797, 99463, … (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.[2]

More generally, an integer w is a Wieferich number to base a, if aφ(w) ≡ 1 (mod w2).[63]:31

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:[64]

21, 39, 55, 57, 105, 111, 147, 155, 165, 171, 183, 195, 201, 203, 205, 219, 231, 237, 253, 273, 285, 291, 301, 305, 309, 327, 333, 355, 357, 385, 399, … (sequence A182297 in OEIS)

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

Lucas-Wieferich primes[edit]

A Lucas-Wieferich prime associated with the pair of integers (P, Q) is a prime p such that Up-ε(P, Q) ≡ 0 (mod p2), where Un(P, Q) denotes the Lucas sequence of the first kind and ε equals the Legendre symbol of P2 - 4Q modulo p. All Wieferich primes are Lucas-Wieferich primes associated with the pair (3, 2).[3]:2088

Fibonacci-Wieferich primes[edit]

Let Q = -1, P be any natural number, these primes are called P-Fibonacci-Wieferich primes or P-Wall-Sun-Sun primes, and if P = 1, they are called Fibonacci-Wieferich primes, and if P = 2, they are called Pell-Wieferich primes. For example, 241 is a Wieferich prime when P = 3, so it is a 3-Fibonacci-Wieferich prime or 3-Wall-Sun-Sun prime. In fact, 3 is an n-Fibonacci-Wieferich prime if and only if n congruent to 0, 4, or 5 (mod 9), like the traditional Wieferich primes, 3 is a base n Wieferich prime if and only if n congruent to 1 or 8 (mod 9).

Wieferich places[edit]

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 qv of K and a ∈ K, with v(a) = 0 then v(aqv-1-1) ≥ 1. v is called a Wieferich place for base a, if v(aqv-1-1) > 1, an elliptic Wieferich place for base PE, if NvPE2 and a strong elliptic Wieferich place for base PE if nvPE2, where nv is the order of P modulo v and Nv gives the number of rational points (over the residue field of v) of the reduction of E at v.[65]:206

See also[edit]

References[edit]

  1. ^ Franco, Z.; Pomerance, C. (1995), On a conjecture of Crandall concerning the qx+1 problem, Math. Of Comput. (American Mathematical Society) 64 (211): 1333–1336, doi:10.2307/2153499. 
  2. ^ a b Banks, W. D.; Luca, F.; Shparlinski, I. E. (2007), Estimates for Wieferich numbers, The Ramanujan Journal (Springer) 14 (3): 361–378, doi:10.1007/s11139-007-9030-z. 
  3. ^ a b McIntosh, R. J.; Roettger, E. L. (2007), A search for Fibonacci-Wieferich and Wolstenholme primes, Mathematics of Computation (AMS) 76 (260): 2087–2094, doi:10.1090/S0025-5718-07-01955-2, archived from the original on 2010-12-10 
  4. ^ The Prime Glossary: Wieferich prime 
  5. ^ Israel Kleiner (2000), From Fermat to Wiles: Fermat's Last Theorem Becomes a Theorem, Elem. Math. 55: 21, doi:10.1007/PL00000079. Archived at WebCite
  6. ^ Leonhard Euler (1736), Theorematum quorundam ad numeros primos spectantium demonstratio, Novi Comm. Acad. Sci. Petropol. (in Latin) 8: 33–37. 
  7. ^ Dickson, L. E. (1917), Fermat's Last Theorem and the Origin and Nature of the Theory of Algebraic Numbers, Annals of Mathematics 18 (4): 161–187, doi:10.2307/2007234 
  8. ^ a b Wilfrid Keller; Jörg Richstein (2005), Solutions of the congruence ap−1 ≡ 1 (mod pr), Math. Comp. 74 (250): 927–936, doi:10.1090/S0025-5718-04-01666-7. 
  9. ^ Bachmann, P. (1913). "Über den Rest von \tfrac{2^{p-1}-1}{p}\,\bmod\,p". Journal für Mathematik (in German) 142 (1): 41–50. 
  10. ^ a b Meissner, W. (1913), Über die Teilbarkeit von 2p − 2 durch das Quadrat der Primzahl p=1093, Sitzungsber. D. Königl. Preuss. Akad. D. Wiss. (in German) (Berlin), Zweiter Halbband. Juli bis Dezember: 663–667 
  11. ^ Haentzschel, E. (1926), Über die Kongruenz 21092 ≡ 1 (mod 10932), Jahresbericht der Deutschen Mathematiker-Vereinigung (in German) 34: 284 
  12. ^ Haentzschel, E. (1925), Über die Kongruenz 21092 ≡ 1 (mod 10932), Jahresbericht der Deutschen Mathematiker-Vereinigung (in German) 34: 184 
  13. ^ Ribenboim, P. (1983), 1093, The Mathematical Intelligencer 5 (2): 28–34, doi:10.1007/BF03023623 
  14. ^ Beeger, N. G. W. H. (1922), On a new case of the congruence 2p − 1 ≡ 1 (mod p2), Messenger of Mathematics 51: 149–150 Archived at WebCite
  15. ^ Guy, R. K. (1965), A property of the prime 3511, The Mathematical Gazette 49 (367): 78–79, doi:10.2307/3614249 
  16. ^ Kravitz, S. (1960). "The Congruence 2p-1 ≡ 1 (mod p2) for p < 100,000". Math. Comp. 14: 378. doi:10.1090/S0025-5718-1960-0121334-7. 
  17. ^ Fröberg C. E. (1958). "Some Computations of Wilson and Fermat Remainders". Math. Comp. 12: 281. doi:10.1090/S0025-5718-58-99270-6. 
  18. ^ Riesel, H. (1964). "Note on the Congruence ap-1 ≡ 1 (mod p2)". Math. Comp. 18: 149–150. doi:10.1090/S0025-5718-1964-0157928-6. 
  19. ^ Lehmer, D. H.. "On Fermat's quotient, base two". Math. Comp. 36 (153): 289–290. doi:10.1090/S0025-5718-1981-0595064-5. 
  20. ^ a b Ribenboim, Paulo (2004), Die Welt der Primzahlen: Geheimnisse und Rekorde (in German), New York: Springer, p. 237, ISBN 3-540-34283-4 
  21. ^ a b c Dorais, F. G.; Klyve, D. (2011). "A Wieferich Prime Search Up to 6.7×1015". Journal of Integer Sequences 14 (9). Zbl 05977305. Retrieved 2011-10-23. 
  22. ^ PrimeGrid Announcement of Wieferich and Wall-Sun-Sun searches
  23. ^ PrimeGrid Wieferich prime search server statistics
  24. ^ a b Crandall, Richard E.; Dilcher, Karl; Pomerance, Carl (1997), A search for Wieferich and Wilson primes, Math. Comput. 66 (217): 433–449, doi:10.1090/S0025-5718-97-00791-6. 
  25. ^ Wieferich, A. (1909), Zum letzten Fermat'schen Theorem, Journal für die reine und angewandte Mathematik (in German) 136 (136): 293–302, doi:10.1515/crll.1909.136.293. 
  26. ^ Coppersmith, D. (1990), Fermat's Last Theorem (Case I) and the Wieferich Criterion, Math. Comp. (AMS) 54 (190): 895–902, doi:10.1090/s0025-5718-1990-1010598-2, JSTOR 2008518. 
  27. ^ Cikánek, P. (1994), A Special Extension of Wieferich's Criterion, Math. Comp. (AMS) 62 (206): 923–930, doi:10.2307/2153550, JSTOR 3562296. 
  28. ^ a b Dilcher, K.; Skula, L. (1995), A new criterion for the first case of Fermat's last theorem, Math. Comp. (AMS) 64 (209): 363–392, doi:10.1090/s0025-5718-1995-1248969-6, JSTOR 2153341 
  29. ^ Mirimanoff, D. (1910), Sur le dernier théorème de Fermat, Comptes rendus hebdomadaires des séances de l'Académie des sciences (in French) 150: 293–206. 
  30. ^ a b c d Granville, A.; Monagan, M. B. (1988), The First Case of Fermat's Last Theorem is true for all prime exponents up to 714,591,416,091,389, Transactions of the American Mathematical Society 306 (1): 329–359, doi:10.1090/S0002-9947-1988-0927694-5. 
  31. ^ Suzuki, Jiro (1994), On the generalized Wieferich criteria, Proc. Japan Acad. Ser. A Math. Sci. 70: 230–234, doi:10.3792/pjaa.70.230 
  32. ^ Charles, D. X. On Wieferich primes
  33. ^ 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 
  34. ^ a b DeKoninck, J.-M.; Doyon, N. (2007), On the set of Wieferich primes and of its complement, Annales Univ. Sci. Budapest., Sect. Comp. 27: 3–13 
  35. ^ Broughan, K. (2006), Relaxations of the ABC Conjecture using integer k 'th roots, New Zealand J. Math. 35 (2): 121–136 
  36. ^ Ribenboim, P. (1979). 13 Lectures on Fermat's Last Theorem. New York: Springer. p. 154. ISBN 0-387-90432-8. 
  37. ^ Mersenne Primes: Conjectures and Unsolved Problems 
  38. ^ Rotkiewicz, A. (1965). "Sur les nombres de Mersenne dépourvus de diviseurs carrés et sur les nombres naturels n, tels que n2∣2n-2". Mat. Vesnik (in French) 2 (17): 78–80. 
  39. ^ Ribenboim, Paulo (1991), The little book of big primes, New York: Springer, p. 64, ISBN 0-387-97508-X 
  40. ^ Bray, H. G.; Warren, L. J. (1967), On the square-freeness of Fermat and Mersenne numbers, Pacific J. Math. 22 (3): 563–564, doi:10.2140/pjm.1967.22.563, MR 0220666, Zbl 0149.28204 
  41. ^ Scott, R.; Styer, R. (April 2004). "On px-qy=c and related three term exponential Diophantine equations with prime bases". Journal of Number Theory (Elsevier) 105 (2): 212–234. doi:10.1016/j.jnt.2003.11.008. 
  42. ^ Scott, R.; Styer, R. (2006). "On the generalized Pillai equation ±ax±by=c". Journal of Number Theory 118 (2): 236–265. doi:10.1016/j.jnt.2005.09.001. 
  43. ^ Wells Johnson (1977), On the nonvanishing of Fermat quotients (mod p), J. Reine angew. Math. 292: 196–200 
  44. ^ Dobeš, Jan; Kureš, Miroslav (2010), Search for Wieferich primes through the use of periodic binary strings, Serdica Journal of Computing 4: 293–300, Zbl 05896729. 
  45. ^ Ribenboim, P. (2004), "Chapter 2. How to Recognize Whether a Natural Number is a Prime", The Little Book of Bigger Primes, New York: Springer-Verlag New York, Inc., p. 99, ISBN 0-387-20169-6  Archived at WebCite
  46. ^ Pinch, R. G. E. (2000). "The Pseudoprimes up to 1013". Lecture Notes in Computer Science 1838: 459–473. doi:10.1007/10722028_30. 
  47. ^ Aebi, C.; Cairns, G. (2008). "Catalan numbers, primes and twin primes". Elemente der Mathematik 63 (4): 153–164. doi:10.4171/EM/103.  Archived at WebCite
  48. ^ a b Ehrlich, A. (1994), Cycles in Doubling Diagrams mod m, The Fibonacci Quarterly 32 (1): 74–78. 
  49. ^ Byeon, D. (2006), Class numbers, Iwasawa invariants and modular forms, Trends in Mathematics 9 (1): 25–29 
  50. ^ Jakubec, S. (1995), Connection between the Wieferich congruence and divisibility of h+, Acta Arithmetica 71 (1): 55–64 
  51. ^ Jakubec, S. (1998), On divisibility of the class number h+ of the real cyclotomic fields of prime degree l, Mathematics of Computation 67 (221): 369–398, doi:10.1090/s0025-5718-98-00916-8 
  52. ^ Joshua Knauer; Jörg Richstein (2005), The continuing search for Wieferich primes, Math. Comp. 74 (251): 1559–1563, doi:10.1090/S0025-5718-05-01723-0. 
  53. ^ About project Wieferich@Home
  54. ^ PrimeGrid, Wieferich & near Wieferich primes p < 11e15
  55. ^ Ribenboim, Paulo (2000), My numbers, my friends: popular lectures on number theory, New York: Springer, pp. 213–229, ISBN 978-0-387-98911-2 
  56. ^ a b Kiss, E.; Sándor, J. (2004). "On a congruence by János Bolyai, connected with pseudoprimes". Mathematica Pannonica 15 (2): 283–288. 
  57. ^ Fermat Quotient at The Prime Glossary
  58. ^ Wieferich primes to base 1052
  59. ^ Wieferich primes to base 10125
  60. ^ Fermat quotients qp(a) that are divisible by p at the Wayback Machine (archived August 9, 2014)
  61. ^ Wieferich primes with level >= 3
  62. ^ Weisstein, Eric W., "Double Wieferich Prime Pair", MathWorld.
  63. ^ Agoh, T.; Dilcher, K.; Skula, L. (1997), Fermat Quotients for Composite Moduli, Journal of Number Theory 66 (1): 29–50, doi:10.1006/jnth.1997.2162 
  64. ^ Müller, H. (2009). "Über Periodenlängen und die Vermutungen von Collatz und Crandall". Mitteilungen der Mathematischen Gesellschaft in Hamburg (in German) (Mathematische Gesellschaft in Hamburg) 28: 121–130. 
  65. ^ Voloch, J. F. (2000), Elliptic Wieferich Primes, Journal of Number Theory 81: 205–209, doi:10.1006/jnth.1999.2471 

Further reading[edit]

External links[edit]