This site is supported by donations to The OEIS Foundation.

# Fermat pseudoprimes

A Fermat pseudoprime ${\displaystyle \scriptstyle q\,}$, to a given base ${\displaystyle \scriptstyle a\,}$ coprime to ${\displaystyle \scriptstyle q\,}$, is a composite number that satisfies the congruence ${\displaystyle \scriptstyle a^{q-1}\,\equiv \,1{\pmod {q}}\,}$ (from Fermat's little theorem.) There are infinitely many such pseudoprimes, they are "sparsely distributed," enabling the theorem to be used as a reasonable step in primality testing [1] (although not sufficient for primality proving.)

The Fermat pseudoprimes to base 2 are referred to as the Poulet numbers.

It is sufficient that the base ${\displaystyle \scriptstyle a\,}$ satisfies ${\displaystyle \scriptstyle 2\,\leq \,a\,\leq \,q-2\,}$ because every odd number ${\displaystyle \scriptstyle q\,}$ satisfies ${\displaystyle \scriptstyle a^{q-1}\,\equiv \,1{\pmod {q}}\,}$ for ${\displaystyle \scriptstyle a\,=\,q-1.\,}$[2] This is simple to see since ${\displaystyle \scriptstyle q-1\,\equiv \,-1{\pmod {q}}\,}$ and thus ${\displaystyle \scriptstyle (q-1)^{q-1}\,\equiv \,(-1)^{q-1}\,\equiv \,1{\pmod {q}}\,}$ since ${\displaystyle \scriptstyle q-1\,}$ is even.

It is furthermore sufficient that the base ${\displaystyle \scriptstyle a\,}$ satisfies ${\displaystyle \scriptstyle 2\,\leq \,a\,\leq \,{\frac {q-1}{2}}\,}$ because every odd number ${\displaystyle \scriptstyle q\,}$ satisfies ${\displaystyle \scriptstyle (q-a)^{q-1}\,\equiv \,a^{q-1}{\pmod {q}},\,1\,\leq \,a\,\leq \,{\frac {q-1}{2}}\,}$. This is simple to see since ${\displaystyle \scriptstyle q-a\,\equiv \,-a{\pmod {q}}\,}$ and thus ${\displaystyle \scriptstyle (q-a)^{q-1}\,\equiv \,(-a)^{q-1}\,\equiv \,a^{q-1}{\pmod {q}}\,}$ since ${\displaystyle \scriptstyle q-1\,}$ is even.

To every odd Fermat pseudoprime ${\displaystyle \scriptstyle q\,}$ exists an even number of bases ${\displaystyle \scriptstyle a\,}$. Every base ${\displaystyle \scriptstyle a\,}$ has a cobase ${\displaystyle \scriptstyle a'\,=\,q-a\,}$.

Examples:

15 is a Fermat pseudoprime to the bases 4 and 11
49 is a Fermat pseudoprime to the bases 18, 19, 30 and 31

If ${\displaystyle \scriptstyle q\,}$ is a Fermat pseudoprime to base ${\displaystyle \scriptstyle a\,}$ then ${\displaystyle \scriptstyle q\,}$ is a Fermat pseudoprime to base ${\displaystyle \scriptstyle b\cdot q+a\,}$ for every integer ${\displaystyle \scriptstyle b\,\geq \,0\,}$.

Example: 33 is a Fermat pseudoprime to the bases 10 and 23. So ${\displaystyle \scriptstyle q\,=\,33\,}$ is a Fermat pseudoprime to every natural number ${\displaystyle \scriptstyle 33q+10\,}$ (10, 43, 76, 109, ...) and ${\displaystyle \scriptstyle 33q+23\,}$ (23, 56, 89, 122, ...).

The Carmichael numbers (Cf. A002997) are composite numbers ${\displaystyle \scriptstyle q\,}$ such that ${\displaystyle \scriptstyle a^{q-1}\,\equiv \,1{\pmod {q}}\,}$ for all bases ${\displaystyle \scriptstyle a\,}$ coprime to ${\displaystyle \scriptstyle q\,}$.

For example, 561 = 3 × 11 × 17, so 561 is Fermat pseudoprime for all bases ${\displaystyle \scriptstyle a\,}$ coprime to 3, 11, 17.

The following table gives small Fermat pseudoprimes for bases ${\displaystyle \scriptstyle 2\,\leq \,a\,\leq \,10\,}$ (form the A-number as ${\displaystyle \scriptstyle 20128\,+\,a\,}$ for ${\displaystyle \scriptstyle 11\,\leq \,a\,\leq \,10\,}$). Note that some mathematicians don't consider even numbers to be Fermat pseudoprimes even if they pass the congruence test.[3]

Fermat pseudoprimes
${\displaystyle \scriptstyle a\,}$ A-number ${\displaystyle \scriptstyle {\rm {Psp}}_{\rm {Fermat}}(a,\,n),\ n\,\geq \,1,\,}$ sequences
2 A001567 {341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, ...}
3 A005935 {91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, 11011, 12403, ...}
4 A020136 {15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, ...}
5 A005936 {4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, 11041, 11476, 12801, 13021, 13333, 13981, ...}
6 A005937 {35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ...}
7 A005938 {6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041, 11521, 12025, 13665, 14089, 16725, 16806, ...}
8 A020137 {9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, ...}
9 A020138 {4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, ...}
10 A005939 {9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, ...}

See table of Fermat pseudoprimes for a listing with many more bases.

Some people accept numbers like 4 or 9 as Fermat pseudoprimes.

For every number ${\displaystyle \scriptstyle n\,}$ it is true that ${\displaystyle \scriptstyle 1^{n-1}\,\equiv \,1{\pmod {n}}.\,}$ And ${\displaystyle \scriptstyle 3^{4-1}\,\equiv \,3{\pmod {4}}.\,}$ The problem is, there is no base ${\displaystyle \scriptstyle a\,}$ coprime to 4 between 1 and 3.

For every odd number ${\displaystyle \scriptstyle n\,}$ it is true that ${\displaystyle \scriptstyle 1^{n-1}\,\equiv \,1{\pmod {n}}\,}$ and ${\displaystyle \scriptstyle (n-1)^{n-1}\,\equiv \,1{\pmod {n}}\,}$. 9 has two coprime bases (and their two cobases) ${\displaystyle \scriptstyle a\,}$ between 1 and 8, namely 2 (≡ 7) and 4 (≡ 5), with ${\displaystyle \scriptstyle 2^{9-1}\,\equiv \,4{\pmod {9}}\,}$ and ${\displaystyle \scriptstyle 4^{9-1}\,\equiv \,7{\pmod {9}}\,}$.

A181780 contains only the Fermat pseudoprimes to some (at least two) bases ${\displaystyle \scriptstyle a,\,2\,\leq \,a\,\leq \,n-2.\,}$

{15, 21, 25, 28, 33, 35, 39, 45, 49, 51, 52, 55, 57, 63, 65, 66, 69, 70, 75, 76, 77, 85, 87, 91, 93, 95, 99, 105, 111, 112, 115, 117, 119, 121, 123, 124, 125, 129, 130, 133, 135, 141, 143, ...}

A?????? contains only the odd Fermat pseudoprimes to some (at least two) bases ${\displaystyle \scriptstyle a,\,2\,\leq \,a\,\leq \,n-2.\,}$

{15, 21, 25, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, ...}

A039772 contains only the even Fermat pseudoprimes to some (at least two) bases ${\displaystyle \scriptstyle a,\,2\,\leq \,a\,\leq \,n-2.\,}$

{28, 52, 66, 70, 76, 112, 124, 130, 148, 154, 172, 176, 186, 190, 196, 208, 232, 238, 244, 246, 268, 276, 280, 286, 292, 304, 310, 316, 322, 344, 364, 366, 370, 388, 396, 406, 412, 418, ...}

A090086 Smallest pseudoprime to base n, not necessarily exceeding n.

{4, 341, 91, 15, 4, 35, 6, 9, 4, 9, 10, 65, 4, 15, 14, 15, 4, 25, 6, 21, 4, 21, 22, 25, 4, 9, 26, 9, 4, 49, 6, 25, 4, 15, 9, 35, 4, 39, 38, 39, 4, 205, 6, 9, 4, 9, 46, 49, 4, 21, 10, 51, 4, 55, 6, 15, 4, 57, 15, 341, 4, 9, ...}

Numbers ${\displaystyle \scriptstyle n\,}$ for which there is only one base ${\displaystyle \scriptstyle a\,}$, from 1 to ${\displaystyle \scriptstyle n-1\,}$, such that ${\displaystyle \scriptstyle a^{n-1}\,\equiv \,1{\pmod {n}}\,}$, the base ${\displaystyle \scriptstyle a\,}$ being 1 itself.

Composite numbers ${\displaystyle \scriptstyle n\,}$ such that ${\displaystyle \scriptstyle a^{n-1}\,\equiv \,1{\pmod {n}}\,}$ only when ${\displaystyle \scriptstyle a\,\equiv \,1{\pmod {n}}.\,}$ (See A111305.)

{4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, ...}

Only for odd numbers ${\displaystyle \scriptstyle n\,}$ it is true that ${\displaystyle \scriptstyle (n-1)^{n-1}\,\equiv \,1{\pmod {n}}\,}$. So the members of the following sequence are odd. But not only this. All members of this sequence are a family. It is the sequence of powers of 3 (A000244) with the exception of 1 and 3 (3 being a prime number and 1 a unit)

{9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, ...}

## Notes

1. R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, New York: Springer-Verlag (2001): p. 121.
2. Richard E. Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, New York: Springer-Verlag, 2001, page 132, Theorem 3.4.2.
3. R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, 2nd Ed. New York: Springer-Verlag (2005): p. 132.