|
|
A291554
|
|
Primes q for which there exists a prime p < q such that 2^q == 2^p (mod pq).
|
|
1
|
|
|
31, 73, 89, 109, 113, 127, 151, 157, 193, 233, 241, 257, 281, 307, 313, 331, 337, 353, 397, 433, 457, 499, 577, 593, 601, 641, 673, 683, 811, 919, 953, 1013, 1049, 1103, 1153, 1163, 1201, 1217, 1249, 1321, 1327, 1399, 1429, 1433, 1459, 1471, 1553, 1601, 1613, 1657, 1709, 1721, 1753, 1777, 1789, 1801, 1873, 1913, 1933, 1993
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Largest prime divisors of pseudoprimes with two distinct prime factors.
All prime divisors of pseudoprimes with two prime factors are all primes except 2, 3, 5, 7, and 13.
|
|
LINKS
|
|
|
FORMULA
|
Equivalent congruences: 2^(pq) == 2 (mod pq), 2^q == 2^p == 2 (mod pq), 2^(q-p) == 1 (mod pq), 2^gcd(p-1,q-1) == 1 (mod pq).
|
|
EXAMPLE
|
We have 2^31 == 2^11 == 2 (mod 11*31), so 31 is a term.
Note that 11*31 = 341 is a pseudoprime.
|
|
MATHEMATICA
|
Select[Prime@ Range[300], Function[p, AnyTrue[Prime@ Range[PrimePi[p] - 1], Function[q, PowerMod[2, q, p q] == PowerMod[2, p, p q]]]]] (* Michael De Vlieger, Aug 27 2017 *)
|
|
PROG
|
(PARI) is(n)=forprime(p=2, n-1, if(Mod(2, p*n)^gcd(n-1, p-1)==1, return(isprime(n)))); 0 \\ Charles R Greathouse IV, Aug 26 2017
(PARI) is(n)=if(n<9 || !isprime(n), return(0)); my(t=Mod(1, znorder(Mod(2, n))), nm1=n-1); t=chinese(t, Mod(1, 2)); forstep(p=lift(t), n-2, t.mod, if(isprime(p) && Mod(2, p*n)^gcd(nm1, p-1)==1, return(1))); 0 \\ Charles R Greathouse IV, Aug 31 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|