TOPICS
Search

Fermat Pseudoprime


A Fermat pseudoprime to a base a, written psp(a), is a composite number n such that a^(n-1)=1 (mod n), i.e., it satisfies Fermat's little theorem. Sometimes the requirement that n must be odd is added (Pomerance et al. 1980) which, for example would exclude 4 from being considered a psp(5).

psp(2)s are called Poulet numbers or, less commonly, Sarrus numbers or Fermatians (Shanks 1993). The following table gives the first few Fermat pseudoprimes to some small bases b.

bOEISb-Fermat pseudoprimes
2A001567341, 561, 645, 1105, 1387, 1729, 1905, ...
3A00593591, 121, 286, 671, 703, 949, 1105, 1541, 1729, ...
4A02013615, 85, 91, 341, 435, 451, 561, 645, 703, ...
5A0059364, 124, 217, 561, 781, 1541, 1729, 1891, ...

If base 3 is used in addition to base 2 to weed out potential composite numbers, only 4709 composite numbers remain <25×10^9. Adding base 5 leaves 2552, and base 7 leaves only 1770 composite numbers.

The following table gives the number of Fermat pseudoprimes to various small bases less than 10, 10^2, 10^3, ....

base(s)OEISFermat pseudoprimes less than 10, 10^2, ...
2A0555500, 0, 3, 22, 78, 245, 750, 2057, ...
2, 3A1142460, 0, 0, 7, 23, 66, 187, 485, ...
2, 3, 5A1142480, 0, 0, 4, 11, 36, 95, 257, ...
2, 3, 5, 7A1142500, 0, 0, 0, 3, 19, 63, 175, ...
3A1142450, 1, 6, 23, 78, 246, 760, 2155, ...
5A1142471, 1, 5, 20, 73, 248, 745, 1954, ...
7A1142491, 2, 6, 16, 73, 234, 659, 1797, ...

See also

Carmichael Number, Fermat's Little Theorem, Poulet Number, Pseudoprime

Explore with Wolfram|Alpha

References

Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, p. 182, 1998.Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25·10^9." Math. Comput. 35, 1003-1026, 1980. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 115, 1993.Sloane, N. J. A. Sequences A001567/M5441, A005935/M5362, A005936/M3712, A020136, A055550, A114245, A114246, A114247, A114248, A114249, and A114250 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Fermat Pseudoprime

Cite this as:

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

Subject classifications