cp's OEIS Frontend

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

%I A006970 M5442 #62 Feb 16 2025 08:32:31
%S A006970 341,561,1105,1729,1905,2047,2465,3277,4033,4681,5461,6601,8321,8481,
%T A006970 10261,10585,12801,15709,15841,16705,18705,25761,29341,30121,31621,
%U A006970 33153,34945,41041,42799
%N A006970 Euler pseudoprimes: composite numbers n such that 2^((n-1)/2) == +-1 (mod n).
%C A006970 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 A006970 Equivalently, these are composites n such that ((n-1)/2)^((n-1)/2) == +-1 (mod n). - _Thomas Ordowski_, Nov 28 2023
%D A006970 R. K. Guy, Unsolved Problems in Number Theory, A12.
%D A006970 C. Schick, Weiche Primzahlen und das 257-Eck, 2008, pages 140-146.
%D A006970 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006970 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 A006970 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EulerPseudoprime.html">Euler Pseudoprime.</a>
%H A006970 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%t A006970 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 A006970 (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 A006970 nonn,nice
%O A006970 1,1
%A A006970 _N. J. A. Sloane_, _Robert G. Wilson v_, _Richard Pinch_
%E A006970 a(15) corrected (to 10261 from 10241) by Faron Moller (fm(AT)csd.uu.se)
%E A006970 Name edited by _Thomas Ordowski_, Nov 28 2023