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,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

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

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

Cf. A001567, A214305, A216838.

Sequence in context: A210548 A146353 A131633 * A084655 A384227 A083988

Adjacent sequences: A291551 A291552 A291553 * A291555 A291556 A291557

Keyword

nonn

Author

Thomas Ordowski, Aug 26 2017

Extensions

More terms from Robert Israel, Aug 26 2017

Status

approved