This site is supported by donations to The OEIS Foundation.

# Fermat pseudoprimes

### From OeisWiki

A **Fermat pseudoprime** , to a given base coprime to , is a composite number that satisfies the congruence (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.)

#### Poulet numbers

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

### Restriction

It is sufficient that the base satisfies because every odd number satisfies for ^{[2]} This is simple to see since and thus since is even.

It is furthermore sufficient that the base satisfies because every odd number satisfies . This is simple to see since and thus since is even.

### Odd Fermat pseudoprimes

To every odd Fermat pseudoprime exists an even number of bases . Every base has a cobase .

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 is a Fermat pseudoprime to base then is a Fermat pseudoprime to base for every integer .

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

### Carmichael numbers

The Carmichael numbers (Cf. A002997) are composite numbers such that for all bases coprime to .

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

## Sequences

### Fermat pseudoprimes sequences

The following table gives small **Fermat pseudoprimes** for bases (form the A-number as for ). Note that some mathematicians don't consider even numbers to be Fermat pseudoprimes even if they pass the congruence test.^{[3]}

A-number
| 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.

### Numbers n which are Fermat pseudoprimes to some base a, 2 ≤ a ≤ n-2

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

For every number it is true that And The problem is, there is no base coprime to 4 between 1 and 3.

For every odd number it is true that and . 9 has two coprime bases (and their two cobases) between 1 and 8, namely 2 (≡ 7) and 4 (≡ 5), with and .

A181780 contains only the Fermat pseudoprimes to some (at least two) bases

- {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

- {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

- {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, ...}

### Composite numbers n such that a^(n-1) ≡ 1 (mod n) only when a ≡ 1 (mod n)

Numbers for which there is only one base , from 1 to , such that , the base being 1 itself.

Composite numbers such that only when (Cf. 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, ... }

### Composite numbers n such that a^(n-1) ≡ 1 (mod n) only when a ≡ 1 (mod n) or a ≡ n-1 (mod n)

Only for odd numbers it is true that . 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, ...}

### Carmichael numbers sequence

The Carmichael numbers: composite numbers n such that a^{n-1} = 1 ( mod n) if a is prime to n. (Cf. A002997)

- {561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, ...}

## See also

## Notes

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