A227136 Fermat pseudoprimes to base 2 which are not Euler pseudoprimes to base 2.

645, 1387, 2701, 2821, 4369, 4371, 7957, 8911, 11305, 13741, 13747, 13981, 14491, 18721, 19951, 23001, 23377, 30889, 31417, 31609, 35333, 39865, 41665, 55245, 57421, 60701, 60787, 63973, 68101, 72885, 83665, 88561, 91001, 93961, 101101, 107185, 121465

Offset: 1

Author

José María Grau Ribas, Jul 02 2013

Keywords

• nonn

Comments

These numbers can be factored by finding k = 2^((n-1)/2) mod n and taking gcd(k-1, n) and gcd(k+1, n). This is a special case of Kraitchik's method. - Charles R Greathouse IV, Dec 27 2013

Numbers n such that 2^(n-1) == 1 (mod n) and 2^((n-1)/2) != +-1 (mod n). - Thomas Ordowski, Feb 25 2016

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Eric W. Weisstein, MathWorld: Euler Pseudoprime
• Eric W. Weisstein, MathWorld: Fermat Pseudoprime

Crossrefs

Cf. A001567, A006970.

Programs

Mathematica

Select[Range[1000000], PowerMod[2, #-1, #] == 1 && ! PowerMod[2, (#-1)/2, #] == 1 && ! PowerMod[2, (#-1)/2, #] == # -1 &]

PARI

is(n)=my(k=Mod(2,n)^(n\2)); k^2==1 && n%2 && k!=1 && k!=-1 \\ Charles R Greathouse IV, Dec 27 2013