Fermat pseudoprimes

A Fermat pseudoprime $\scriptstyle q\,$, to a given base $\scriptstyle a\,$ coprime to $\scriptstyle q\,$, is a composite number that satisfies the congruence $\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 (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 $\scriptstyle a\,$ satisfies $\scriptstyle 2\,\leq \,a\,\leq \,q-2\,$ because every odd number $\scriptstyle q\,$ satisfies $\scriptstyle a^{q-1}\,\equiv \,1{\pmod {q}}\,$ for $\scriptstyle a\,=\,q-1.\,$ This is simple to see since $\scriptstyle q-1\,\equiv \,-1{\pmod {q}}\,$ and thus $\scriptstyle (q-1)^{q-1}\,\equiv \,(-1)^{q-1}\,\equiv \,1{\pmod {q}}\,$ since $\scriptstyle q-1\,$ is even.

It is furthermore sufficient that the base $\scriptstyle a\,$ satisfies $\scriptstyle 2\,\leq \,a\,\leq \,{\frac {q-1}{2}}\,$ because every odd number $\scriptstyle q\,$ satisfies $\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 $\scriptstyle q-a\,\equiv \,-a{\pmod {q}}\,$ and thus $\scriptstyle (q-a)^{q-1}\,\equiv \,(-a)^{q-1}\,\equiv \,a^{q-1}{\pmod {q}}\,$ since $\scriptstyle q-1\,$ is even.

To every odd Fermat pseudoprime $\scriptstyle q\,$ exists an even number of bases $\scriptstyle a\,$. Every base $\scriptstyle a\,$ has a cobase $\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 $\scriptstyle q\,$ is a Fermat pseudoprime to base $\scriptstyle a\,$ then $\scriptstyle q\,$ is a Fermat pseudoprime to base $\scriptstyle b\cdot q+a\,$ for every integer $\scriptstyle b\,\geq \,0\,$.

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

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

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

The following table gives small Fermat pseudoprimes for bases $\scriptstyle 2\,\leq \,a\,\leq \,10\,$ (form the A-number as $\scriptstyle 20128\,+\,a\,$ for $\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.

Fermat pseudoprimes

$\scriptstyle a\,$	A-number	$\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 $\scriptstyle n\,$ it is true that $\scriptstyle 1^{n-1}\,\equiv \,1{\pmod {n}}.\,$ And $\scriptstyle 3^{4-1}\,\equiv \,3{\pmod {4}}.\,$ The problem is, there is no base $\scriptstyle a\,$ coprime to 4 between 1 and 3.

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

A181780 contains only the Fermat pseudoprimes to some (at least two) bases $\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 $\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 $\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 $\scriptstyle n\,$ for which there is only one base $\scriptstyle a\,$, from 1 to $\scriptstyle n-1\,$, such that $\scriptstyle a^{n-1}\,\equiv \,1{\pmod {n}}\,$, the base $\scriptstyle a\,$ being 1 itself.

Composite numbers $\scriptstyle n\,$ such that $\scriptstyle a^{n-1}\,\equiv \,1{\pmod {n}}\,$ only when $\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 $\scriptstyle n\,$ it is true that $\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, ...}

See also

• Pseudoprimes