A356638 Odd composite numbers k such that 2^((k-1)/2) == -1 (mod k).

3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 476971, 489997, 800605, 838861, 873181, 877099, 1004653, 1251949, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1678541, 1811573, 1907851, 1987021, 2004403, 2269093

Offset: 1

Author

Jeppe Stig Nielsen, Aug 19 2022

Keywords

• nonn

Comments

Counterexamples (pseudoprimes) to the hypothesis that this congruence is sufficient to prove that an odd number is prime.

Compare with Proth's theorem.

Crossrefs

Cf. A244626, A244628.

Programs

Mathematica

Select[Range[1, 2.5*10^6, 2], CompositeQ[#] && PowerMod[2, (# - 1)/2, #] == # - 1 &] (* Amiram Eldar, Aug 19 2022 *)

PARI

forstep(k=3,10^8,2,isprime(k)&&next();Mod(2,k)^((k-1)/2)==-1&&print1(k,", "))