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

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A001567, A006970.

Sequence in context: A168626 A216023 A100873 * A216364 A063844 A265684

Adjacent sequences: A227133 A227134 A227135 * A227137 A227138 A227139

Keyword

nonn

Author

José María Grau Ribas, Jul 02 2013

Status

approved