Fermat Pseudoprime

A Fermat pseudoprime to a base $a$, written psp($a$), is a Composite Number $n$ such that $a^{n-1}\equiv 1\ \left({{\rm mod\ } {n}}\right)$ (i.e., it satisfies Fermat's Little Theorem, sometimes with the requirement that $n$ must be Odd; Pomerance et al. 1980). psp(2)s are called Poulet Numbers or, less commonly, Sarrus Numbers or Fermatians (Shanks 1993). The first few Even psp(2)s (including the Prime 2 as a pseudoprime) are 2, 161038, 215326, ... (Sloane's A006935).

If base 3 is used in addition to base 2 to weed out potential Composite Numbers, only 4709 Composite Numbers remain $<25\times 10^9$. Adding base 5 leaves 2552, and base 7 leaves only 1770 Composite Numbers.

See also Fermat's Little Theorem, Poulet Number, Pseudoprime

References

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 ftp://sable.ox.ac.uk/pub/math/primes/ps2.Z.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 115, 1993.

Sloane, N. J. A. Sequence A006935/M2190 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.