Fermat's pseudoprime number

A natural number n is called Fermat's pseudoprime number (for base a ) if it is a composite number that behaves like a prime number with respect to a base a that is relatively prime to n : namely, if congruence

${\displaystyle a^{n-1}\equiv 1\mod n}$

for the number a coprime to n is fulfilled.

In other words, n must divide the difference . ${\displaystyle a^{n-1}-1}$

For example, 341 is a Fermatian pseudoprime with base 2, since 341 is a divisor of , but not prime due to 341 = 11 * 31. ${\displaystyle 2^{340}-1}$

A Fermat's pseudoprime is a pseudoprime related to the criterion of Fermat's small theorem . This criterion is used in Fermat's primality test.

definition

A Fermat pseudoprime with base a is a composite, natural number n for which

${\displaystyle a^{n-1}\equiv 1\mod n}$

applies. With respect to the base a , n behaves like a prime number.

Example: The number 91 is a Fermat pseudo-prime number with respect to the bases 17, 29 and 61, as , and are divisible by the 91st Although the number 91 is not a prime number (91 = 7 · 13), it fulfills Fermat's little theorem for some a . ${\displaystyle 17^{90}-1}$ ${\displaystyle 29^{90}-1}$ ${\displaystyle 61^{90}-1}$

Subclasses and properties

Fermat's pseudoprimes include the Carmichael numbers , Euler's pseudoprimes, and Euler's absolute pseudoprimes.

If n is a Fermat pseudoprime number with base a , then also with base a ^k and with a + kn ( k> 1 ), and - if n is odd and a <n - with base n - a .

Table with Fermat's pseudoprimes

For every basis there are an infinite number of Fermatsche pseudoprimes. The following is a table of the smallest Fermat's pseudoprimes (at least less than or equal to 10000) based on a :

a	Fermat's pseudoprimes n based on a	OEIS episode
1	4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, ... (any composite integer)	(Follow A002808 in OEIS )
2	341, 561 , 645, 1105 , 1387, 1729 , 1905, 2047, 2465 , 2701, 2821 , 3277, 4033, 4369, 4371, 4681, 5461, 6601 , 7957, 8321, 8481, 8911 , 10261, ...	(Follow A001567 in OEIS )
3	91, 121, 286, 671, 703, 949, 1105 , 1541, 1729 , 1891, 2465 , 2665, 2701, 2821 , 3281, 3367, 3751, 4961, 5551, 6601 , 7381, 8401, 8911 , 10585, ...	(Follow A005935 in OEIS )
4th	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, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601 , 6643, 7957, 8321, 8481, 8695, 8911 , 9061, 9131, 9211, 9605, 9919, 10261, ...	(Follow A020136 in OEIS )
5	4, 124, 217, 561 , 781, 1541, 1729 , 1891, 2821 , 4123, 5461, 5611, 5662, 5731, 6601 , 7449, 7813, 8029, 8911 , 9881, 11041, ...	(Follow A005936 in OEIS )
6th	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, 10585, ...	(Follow A005937 in OEIS )
7th	6, 25, 325, 561 , 703, 817, 1105 , 1825, 2101, 2353, 2465 , 3277, 4525, 4825, 6697, 8321, 10225, ...	(Follow A005938 in OEIS )
8th	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, 1905, 2047, 2169, 2465 , 2501, 2701, 2821 , 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601 , 6951, 7107, 7161, 7957, 8321, 8481, 8911 , 9265, 9709, 9773, 9881, 9945, 10261, ...	(Follow A020137 in OEIS )
9	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 , 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601 , 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911 , 10585, ...	(Follow A020138 in OEIS )
10	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, 8401, 8911 , 10001, 11111, ...	(Follow A005939 in OEIS )
11	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105 , 1330, 1729 , 2047, 2257, 2465 , 2821 , 4577, 4921, 5041, 5185, 6601 , 7869, 8113, 8170, 8695, 8911 , 9730, 10585, ...	(Follow A020139 in OEIS )
...	...

For Fermatsche pseudoprimes for bases 12 to 100 see (sequence A020140 in OEIS ) to (sequence A020228 in OEIS ). For all other bases up to a = 165 see pseudoprimes: Table Fermatsche pseudoprimes on Wikibooks.

The seven bold numbers 561, 1105, 1729, 2465, 2821, 6601, 8911 are Fermat Pseudoprimes to all prime bases a . If they do not appear at certain bases a , it is because they are not coprime to these bases a (for example 561 does not appear at base a = 6 because is). ${\displaystyle \operatorname {ggT} (6,561)=3\not =1}$

Numbers that are Fermatsche pseudoprimes for all coprime bases a are called Carmichael numbers .

The following applies:

Each to a prime Carmichael number is also simultaneously a pseudo Fermat prime to base a . The converse is not true, that is, there are Fermatian pseudoprimes with base a that are not Carmichael numbers at the same time.

Mathematically, one formulates the above facts using set notation as follows:

{to a coprime Carmichael number} {Fermatsche pseudoprime to base a } ${\displaystyle \subsetneqq }$

Construction of infinitely many Fermatscher pseudoprimes for every basis

Michele Cipolla constructed infinitely many Fermatsche pseudoprimes for each base in the following way in 1904:

For every a> 1 and every odd prime p that does not divide is ${\displaystyle a(a^{2}-1)}$

${\displaystyle n={\frac {a^{p}-1}{a-1}}\cdot {\frac {a^{p}+1}{a+1}}}$

a Fermat pseudoprime with base a . Since there are infinitely many prime numbers, there must be infinitely many Fermatian pseudoprimes for every basis. Examples:

a	p	1st factor	2nd factor	n	Prime factorization
2	5	31	11	341	11 31
2	7th	127	43	5461	43 · 127
3	5	121	61	7381	11 · 11 · 61
3	7th	1093	547	597871	547 1093
7th	5	2801	2101	5884901	11 · 191 · 2801

literature

• Richard Crandall , Carl Pomerance : Prime Numbers. A Computational Perspective. 2nd edition. Springer, New York NY a. a. 2005, ISBN 0-387-25282-7 .

Web links

Wikibooks: Fermatsche pseudoprimes on a certain base α  - learning and teaching materials

• Eric W. Weisstein: Fermat Pseudoprime . MathWorld
• Final Answers Modular Arithmetic

Individual evidence

1. ↑ For the proof, see GH Hardy , EM Wright : An introduction to the theory of numbers , Oxford University Press, 2005, page 90.