A Fermat pseudoprime to a base , written psp(), is a composite number such that , i.e., it satisfies Fermat's little theorem. Sometimes the requirement that 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 .
OEIS | -Fermat pseudoprimes | |
2 | A001567 | 341, 561, 645, 1105, 1387, 1729, 1905, ... |
3 | A005935 | 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, ... |
4 | A020136 | 15, 85, 91, 341, 435, 451, 561, 645, 703, ... |
5 | A005936 | 4, 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 . 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, , , ....
base(s) | OEIS | Fermat pseudoprimes less than 10, , ... |
2 | A055550 | 0, 0, 3, 22, 78, 245, 750, 2057, ... |
2, 3 | A114246 | 0, 0, 0, 7, 23, 66, 187, 485, ... |
2, 3, 5 | A114248 | 0, 0, 0, 4, 11, 36, 95, 257, ... |
2, 3, 5, 7 | A114250 | 0, 0, 0, 0, 3, 19, 63, 175, ... |
3 | A114245 | 0, 1, 6, 23, 78, 246, 760, 2155, ... |
5 | A114247 | 1, 1, 5, 20, 73, 248, 745, 1954, ... |
7 | A114249 | 1, 2, 6, 16, 73, 234, 659, 1797, ... |