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

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

## Individual evidence

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