An Euler-Jacobi pseudoprime to an integer base 
is an odd composite
number 
such that 
and 
are relatively prime and the Jacobi
symbol 
satisfies
 |
(Guy 1994; but note that Guy calls these simply "Euler pseudoprimes"). No odd composite number
is an Euler-Jacobi pseudoprime for all bases 
relatively prime to it.
This class includes some Carmichael numbers
and all strong pseudoprimes to base 
. Every Euler-Jacobi pseudoprime to base 
is an Euler pseudoprime
to that base, but the converse need not hold. For each fixed 
, at most half of the bases 
with 
and 
pass the defining congruence.
The first few base-2 Euler-Jacobi pseudoprimes are 561, 1105, 1729, 1905, 2047, 2465, ... (OEIS A047713), and the first few base-3
Euler-Jacobi pseudoprimes are 121, 703, 1729, 1891, 2821, 3281, 7381, ... (OEIS A048950). The numbers of base-2 Euler-Jacobi pseudoprimes
less than 
,
,
... are 0, 1, 12, 36, 114, ... (OEIS A055551).
." In