This site is supported by donations to The OEIS Foundation.

Fermat pseudoprimes

From OeisWiki
(Redirected from Fermat pseudoprime)
Jump to: navigation, search

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.)

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

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.

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, ...).

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.

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]

Fermat pseudoprimes
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.

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

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 for which there is only one base , from 1 to , such that , the base being 1 itself.

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

See also

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.