An Euler-Jacobi pseudoprime to a base a is an odd composite number n such that (a, n) = 1 and the Jacobi symbol (a/n) satisfies (a/n) congruent a^((n - 1)/2) (mod n) (Guy 1994; but note that Guy calls these simply "Euler pseudoprimes"). No odd composite number is an Euler-Jacobi pseudoprime for all bases a relatively prime to it. This class includes some Carmichael numbers, all strong pseudoprimes to base a, and all Euler pseudoprimes to base a. An Euler pseudoprime is pseudoprime to at most 1/2 of all possible bases less than itself.