OFFSET
1,1
COMMENTS
Numbers that are Fermat pseudoprimes to some base a (2<=a<=n-2) not Euler pseudoprimes to any base a (2<=a<=n-2).
EXAMPLE
4^(15-1) == 1 (mod 15), but 4^((15-1)/2) == 4 (mod 15)
PROG
(PARI)
fsp(n)=
{ /* whether n is Fermat pseudoprime to any base a where 2<=a<=n-2 */
for (a=2, n-2,
if ( gcd(a, n)!=1, next() );
if ( (Mod(a, n))^(n-1)==+1, return(1) )
);
return(0);
}
esp(n)=
{ /* whether n is Euler pseudoprime to any base a where 2<=a<=n-2 */
local(w);
if ( n%2==0, return(0) );
for (a=2, n-2,
if ( gcd(a, n)!=1, next() );
w = abs(component((Mod(a, n))^((n-1)/2), 2));
if ( (w==1) || (w==n-1), return(1) )
);
return(0);
}
for(n=3, 300, if(isprime(n), next()); if( fsp(n) && (!esp(n)) , print1(n, ", ") ); );
CROSSREFS
KEYWORD
nonn
AUTHOR
Karsten Meyer, Dec 31 2010
STATUS
approved