login
Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).
(Formerly M5442)
29

%I M5442 #61 Dec 23 2023 16:42:45

%S 341,561,1105,1729,1905,2047,2465,3277,4033,4681,5461,6601,8321,8481,

%T 10261,10585,12801,15709,15841,16705,18705,25761,29341,30121,31621,

%U 33153,34945,41041,42799

%N Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).

%C Pseudoprimes for the primality test from [Schick]: n odd is probably prime if (n-1) | A003558((n-1)/2). (Succeeds for 99.9975% of odd natural numbers less than 10^8.) - _Jonathan Skowera_, Jun 29 2013

%C Equivalently, these are composites n such that ((n-1)/2)^((n-1)/2) == +-1 (mod n). - _Thomas Ordowski_, Nov 28 2023

%D R. K. Guy, Unsolved Problems in Number Theory, A12.

%D C. Schick, Weiche Primzahlen und das 257-Eck, 2008, pages 140-146.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Amiram Eldar, <a href="/A006970/b006970.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1231 from T. D. Noe)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EulerPseudoprime.html">Euler Pseudoprime.</a>

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

%t ok[_?PrimeQ] = False; ok[n_] := (p = PowerMod[2, (n - 1)/2, n]; p == Mod[1, n] || p == Mod[-1, n]); Select[2 Range[22000] + 1, ok] (* _Jean-François Alcover_, Apr 06 2011 *)

%o (PARI) isok(n) = {if (!isprime(n) && (n%2), npm = Mod(2, n)^((n-1)/2); if ((npm == Mod(1,n)) || (npm == Mod(-1,n)), print1(n, ", ")););} \\ _Michel Marcus_, Sep 12 2015

%K nonn,nice

%O 1,1

%A _N. J. A. Sloane_, _Robert G. Wilson v_, _Richard Pinch_

%E a(15) corrected (to 10261 from 10241) by Faron Moller (fm(AT)csd.uu.se)

%E Name edited by _Thomas Ordowski_, Nov 28 2023