In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Definition
Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a.
In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a. The false statement that all numbers that pass the Fermat primality test for base 2, are prime, is called the Chinese hypothesis.
The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes the Fermat primality test for the base 2.
Pseudoprimes to base 2 are sometimes called Sarrus numbers, after P. F. Sarrus who discovered that 341 has this property, Poulet numbers, after P. Poulet who made a table of such numbers, or Fermatians .
A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood.
An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.
Properties
Distribution
There are infinitely many pseudoprimes to any given base a > 1. In 1904, Cipolla showed how to produce an infinite number of pseudoprimes base a > 1: Let A = (ap - 1)/(a - 1) and let B = (ap + 1)/(a + 1), where p is any odd prime. Then n = AB is composite, and is a pseudoprime to base a. For example, if a = 2 and p = 5, then A = 31, B = 11, and n = 341 is a pseudoprime to base 2.
In fact, there are infinitely many strong pseudoprimes to any base greater than 1 (see Theorem 1 of ) and infinitely many Carmichael numbers, but they are comparatively rare. There are three pseudoprimes to base 2 below 1000, 245 below one million, and 21853 less than 25·109. There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (see Table 1 of ).
Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all Fermat composites and Mersenne composites.
Factorizations
The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the following table.
A Poulet number all of whose divisors d divide 2d − 2 is called a super-Poulet number. There are infinitely many Poulet numbers which are not super-Poulet Numbers.
Smallest Fermat pseudoprimes
The smallest pseudoprime for each base a ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below a are excluded in the table. (For that to allow pseudoprimes below a, see )
List of Fermat pseudoprimes in fixed base n
For more information (base 31 to 100), see to , and for all bases up to 150, see table of Fermat pseudoprimes (text in German), this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n)
Which bases b make n a Fermat pseudoprime?
If composite is even, then is a Fermat pseudoprime to the trivial base . If composite is odd, then is a Fermat pseudoprime to the trivial bases .
For any composite , the number of distinct bases modulo , for which is a Fermat pseudoprime base , is
where are the distinct prime factors of . This includes the trivial bases.
For example, for , this product is . For , the smallest such nontrivial base is .
Every odd composite is a Fermat pseudoprime to at least two nontrivial bases modulo unless is a power of 3.
For composite n < 200, the following is a table of all bases b < n which n is a Fermat pseudoprime. If a composite number n is not in the table (or n is in the sequence ), then n is a pseudoprime only to the trivial base 1 modulo n.
For more information (n = 201 to 5000), see, this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n). When p is a prime, p2 is a Fermat pseudoprime to base b if and only if p is a Wieferich prime to base b. For example, 10932 = 1194649 is a Fermat pseudoprime to base 2, and 112 = 121 is a Fermat pseudoprime to base 3.
The number of the values of b for n are (For n prime, the number of the values of b must be n - 1, since all b satisfy the Fermat little theorem) 1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ...