OFFSET
1,1
COMMENTS
Double Wieferich prime pairs are pairs of prime numbers p and q such that p^(q-1) == 1 (mod q^2) and q^(p-1) == 1 (mod p^2).
Pairs of primes p and q such that A274916(x, y) = 2, where x and y are the indices of p and q in A000040 respectively.
This sequence provides a "complete" listing of double Wieferich prime pairs. A124122 omits values of p where a smaller p with the same value of q in A124121 exists, while A266829 lists each value of p exactly once, regardless of how many values of q exist for that p.
There are two ways to retrieve the pair (p, q) from the data when looking at any specific value:
1. Look at the indices i of the terms. If the index is even, a(i) is the larger member p of a pair, so q is a(i-1). If the index is odd, a(i) is the smaller member q of the pair, so p is a(i+1).
2. Look at a term a(i) in the data section. If a(i-1) and a(i+1) are both larger than a(i), then a(i) is the smaller member of a pair and its partner is a(i+1). If a(i-1) and a(i+1) are both smaller than a(i), then a(i) is the larger member of a pair and its partner is a(i-1).
There are no further pairs with p*q <= 10^15 and p < 2^(1/3)*10^10 and only one additional Wieferich pair, namely (5, 188748146801), is known, but its position in the sequence is uncertain (cf. Logan, Mossinghoff, 2015).
Double Wieferich pairs were first mentioned by Inkeri, who showed that if Catalan's Diophantine equation x^p - y^q = 1 has a solution (x, y) for prime numbers p and q both congruent to 3 modulo 4, p > q and h(p) =/= 0 (mod q), where h(p) is the class number of the field k(sqrt(-p)), then (p, q) is a double Wieferich pair (cf. Inkeri, 1964, Theorem 2).
The pairs (2, 1093) and (83, 4871) were apparently first found by Aaltonen and Inkeri, who state that these two and a third one, (3, 1006003), from a table from Brillhart, Tonascia and Weinberger, are the only pairs they are aware of (cf. Aaltonen, Inkeri, 1991, Remark on p. 365).
The pairs (2903, 18787) and (911, 318917) were first found by Mignotte and Roy (cf. Keller, Richstein, 2005, p. 935) and later also by Ernvall and Metsänkylä in a search to 10^6, who also mention the pair (5, 1645333507) found by Montgomery (cf. Ernvall, Metsänkylä, 1997, p. 1360).
Several further conditions connecting double Wieferich pairs to Catalan's equation were obtained by Steiner, for example the result that if both p and q in a solution to the Catalan equation are congruent to 3 modulo 4 or both p and q satisfy either p == 3 (mod 4) and q == 5 (mod 8) or vice versa, then (p, q) is a double Wieferich pair (cf. Steiner, 1998, Theorems 7 and 8).
Mihailescu further showed that if the Catalan equation has a solution with p and q distinct odd primes and xy != 0, then q^2 | x, p^2 | y and p and q form a double Wieferich prime pair (cf. Mihailescu, 2003, Theorem 1).
If the Diophantine equation p^x - q^y = c has more than one solution with q an odd prime incongruent to 1 modulo 12, p < 2*q, gcd(p-1, q-1) even and (p, q, c) not one of (3, 2, 1), (2, 3, 5), (2, 3, 13), (2, 5, 3) or (13, 3, 10), then (p, q) is a double Wieferich pair (cf. Scott, Styer, 2004, pages 218-219).
Corollary to Proposition 4 in Pomerance, Selfridge, Wagstaff, 1980: Let p and q be primes and let c and d be composites such that c and d are base-p and base-q Fermat pseudoprimes, respectively. If p^2 divides d and q^2 divides c, then (p, q) is a double Wieferich pair.
LINKS
M. Aaltonen and K. Inkeri, Catalan's equation x^p - y^p = 1 and related congruences, Math. Comp. 56 (1991), 359-370.
R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients, Mathematics of Computation 66 (1997), 1353-1365.
K. Inkeri, On Catalan's problem, Acta Arithmetica 9 (1964), 285-290.
W. Keller and J. Richstein, Solutions of the congruence a^p-1 == 1 (mod p^r), Mathematics of Computation, 74 (2005), 927-936.
B. Logan and M. J. Mossinghoff, Double Wieferich pairs and circulant Hadamard matrices, ResearchGate, 2015.
P. Mihailescu, A class number free criterion for catalan's conjecture, Journal of Number Theory, Vol. 99, No. 2 (2003), 225-231.
C. Pomerance, J. L. Selfridge and S. S. Wagstaff, The pseudoprimes to 25 * 10^9, Mathematics of Computation, 35 (1980), 1003-1026.
R. Scott and R. Styer, On p^x-q^y=c and related three term exponential Diophantine equations with prime bases, Journal of Number Theory, Vol. 105, No. 2 (2004), 212-234.
R. Steiner, Class number bounds and Catalan's equation, Mathematics of Computation 67 (1998), 1317-1322.
EXAMPLE
The primes 83 and 4871 satisfy 83^4870 == 1 (mod 23726641) and 4871^82 == 1 (mod 6889), respectively, so 83 and 4871 are terms of the sequence.
PROG
(PARI) is_dwpp(n, k) = Mod(n, k^2)^(k-1)==1 && Mod(k, n^2)^(n-1)==1
search(x, y) = forprime(p=x, y, forprime(q=1, p-1, if(is_dwpp(p, q), print1(q, ", ", p, ", "))))
search(1, 1e6) \\ search pairs in the interval [1, 10^6]
CROSSREFS
KEYWORD
nonn,tabf,hard,more
AUTHOR
Felix Fröhlich, Feb 11 2017
STATUS
approved