|
%I #23 Mar 11 2016 06:22:59
%S 645,1387,2701,2821,4369,4371,7957,8911,11305,13741,13747,13981,14491,
%T 18721,19951,23001,23377,30889,31417,31609,35333,39865,41665,55245,
%U 57421,60701,60787,63973,68101,72885,83665,88561,91001,93961,101101,107185,121465
%N Fermat pseudoprimes to base 2 which are not Euler pseudoprimes to base 2.
%C 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
%C Numbers n such that 2^(n-1) == 1 (mod n) and 2^((n-1)/2) != +-1 (mod n). - _Thomas Ordowski_, Feb 25 2016
%H Charles R Greathouse IV, <a href="/A227136/b227136.txt">Table of n, a(n) for n = 1..10000</a>
%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/EulerPseudoprime.html">MathWorld: Euler Pseudoprime</a>
%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/FermatPseudoprime.html">MathWorld: Fermat Pseudoprime</a>
%t Select[Range[1000000], PowerMod[2, #-1, #] == 1 && ! PowerMod[2, (#-1)/2, #] == 1 && ! PowerMod[2, (#-1)/2, #] == # -1 &]
%o (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
%Y Cf. A001567, A006970.
%K nonn
%O 1,1
%A _José María Grau Ribas_, Jul 02 2013
|
