A291554 Primes q for which there exists a prime p < q such that 2^q == 2^p (mod pq).
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
Offset: 1
Keywords
Examples
We have 2^31 == 2^11 == 2 (mod 11*31), so 31 is a term. Note that 11*31 = 341 is a pseudoprime.
Links
- Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Programs
-
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 *)
-
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
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).
Extensions
More terms from Robert Israel, Aug 26 2017
Comments