Euler-Jacobi Pseudoprime

An Euler-Jacobi pseudoprime to a base $a$ is an Odd Composite numbers such that $(a,n)= 1$ and the Jacobi Symbol $(a/n)$ satisfies

$$\left({a\over n}\right)\equiv a^{(n-1)/2} {\rm\ (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. The first few base-2 Euler-Jacobi pseudoprimes are 561, 1105, 1729, 1905, 2047, 2465, ... (Sloane's A047713).

See also Euler Pseudoprime, Pseudoprime

References

Guy, R. K. ``Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.'' §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Sloane, N. J. A. Sequence A047713/M5461 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.