Fermat pseudoprimes

From OeisWiki

Current revision (unreviewed)

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

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

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.

[0] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, New York: Springer-Verlag (2001): p. 121.

[1] Richard E. Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, New York: Springer-Verlag, 2001, page 132, Theorem 3.4.2.

[2] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, 2nd Ed. New York: Springer-Verlag (2005): p. 132.

[1]

[2]

[3]

Fermat pseudoprimes

From OeisWiki

Contents

Poulet numbers

Restriction

Odd Fermat pseudoprimes

Carmichael numbers

Sequences

Fermat pseudoprimes sequences

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

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

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

Carmichael numbers sequence

See also

Notes

Views

Personal tools

Navigation

Search

Toolbox