info prev up next book cdrom email home


A pseudoprime is a Composite number which passes a test or sequence of tests which fail for most Composite numbers. Unfortunately, some authors drop the ``Composite'' requirement, calling any number which passes the specified tests a pseudoprime even if it is Prime. Pomerance, Selfridge, and Wagstaff (1980) restrict their use of ``pseudoprime'' to Odd Composite numbers. ``Pseudoprime'' used without qualification means Fermat Pseudoprime.

Carmichael Numbers are Odd Composite numbers which are pseudoprimes to every base; they are sometimes called Absolute Pseudoprimes. The following table gives the number of Fermat Pseudoprimes psp, Euler Pseudoprimes epsp, and Strong Pseudoprimes spsp to the base 2, as well as Carmichael Numbers CN which are less the first few powers of 10 (Guy 1994).

  $10^3$ $10^4$ $10^5$ $10^6$ $10^7$ $10^8$ $10^9$ $10^{10}$
psp(2) 3 22 78 245 750 2057 5597 14884
epsp(2) 1 12 36 114 375 1071 2939 7706
spsp(2) 0 5 16 46 162 488 1282 3291
CN 1 7 16 43 105 255 646 1547

See also Carmichael Number, Elliptic Pseudoprime, Euler Pseudoprime, Euler-Jacobi Pseudoprime, Extra Strong Lucas Pseudoprime, Fermat Pseudoprime, Fibonacci Pseudoprime, Frobenius Pseudoprime, Lucas Pseudoprime, Perrin Pseudoprime, Probable Prime, Somer-Lucas Pseudoprime, Strong Elliptic Pseudoprime, Strong Frobenius Pseudoprime, Strong Lucas Pseudoprime, Strong Pseudoprime


Grantham, J. ``Frobenius Pseudoprimes.''

Grantham, J. ``Pseudoprimes/Probable Primes.''

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.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. ``The Pseudoprimes to $25\cdot 10^9$.'' Math. Comput. 35, 1003-1026, 1980. Available electronically from

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein