This site is supported by donations to The OEIS Foundation.

Fermat pseudoprimes

From OeisWiki

(Redirected from Poulet numbers)
Jump to: navigation, search

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 [1] (although not sufficient for primality proving.)

Contents

Poulet numbers

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

Restriction

It is sufficient that the base \scriptstyle a \, satisfies \scriptstyle 2 \,\le\, a \,\le\, q-2 \, because every odd number \scriptstyle q \, satisfies \scriptstyle a^{q-1} \,\equiv\, 1 \pmod q \, for \scriptstyle a \,=\, q-1. \,[2] 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 \,\le\, a \,\le\, \frac{q-1}{2} \, because every odd number \scriptstyle q \, satisfies \scriptstyle (q-a)^{q-1} \,\equiv\, a^{q-1} \pmod q,\, 1 \,\le\, a \,\le\, \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.

Odd Fermat pseudoprimes

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

Carmichael numbers

The Carmichael numbers (Cf. A002997) are composite numbers \scriptstyle q \, such that \scriptstyle a^{n-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.

Sequences

Fermat pseudoprimes sequences

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

Fermat pseudoprimes
\scriptstyle a \, A-number \scriptstyle {\rm Psp}_{\rm Fermat}(a,\, n),\ n \,\ge\, 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.

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 \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 \,\le\, a \,\le\, 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 \,\le\, a \,\le\, 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 \,\le\, a \,\le\, 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, ...}

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

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

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

  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.
Personal tools