TOPICS
Search

Euler-Jacobi Pseudoprime

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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)=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.

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 number of base-2 Euler-Jacobi primes less than 10^2, 10^3, ... are 0, 1, 12, 36, 114, ... (OEIS A055551).

See also

Euler Pseudoprime, Pseudoprime

Explore with Wolfram|Alpha

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.Pinch, R. G. E. "The Pseudoprimes Up to 10^(13)." ftp://ftp.dpmms.cam.ac.uk/pub/PSP/.Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, 1994.Sloane, N. J. A. Sequences A047713/M5461, A048950, and A055551 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Euler-Jacobi Pseudoprime

Cite this as:

Weisstein, Eric W. "Euler-Jacobi Pseudoprime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Euler-JacobiPseudoprime.html

Subject classifications