In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
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 a positive integer a, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a.
3.32 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.
[2] The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the Chinese hypothesis.
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 (sequence A001567 in the OEIS).
An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.[2][1]: Def.
In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base a > 1: let A = (ap - 1)/(a - 1) and let B = (ap + 1)/(a + 1), where p is a prime number that does not divide a(a2 - 1).
In fact, there are infinitely many strong pseudoprimes to any base greater than 1 (see Theorem 1 of [5]) and infinitely many Carmichael numbers,[6] but they are comparatively rare.
There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (see Table 1 of [5]).
Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all Fermat composites and Mersenne composites.
The probability of a composite number n passing the Fermat test approaches zero for
Specifically, Kim and Pomerance showed the following: The probability that a random odd number n ≤ x is a Fermat pseudoprime to a random base
[8] 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 OEIS: A090086) (sequence A007535 in the OEIS) For more information (base 31 to 100), see OEIS: A020159 to OEIS: A020228, 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) If composite
is a Fermat pseudoprime to at least two nontrivial bases modulo
1, p. 1393 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 A209211), then n is a pseudoprime only to the trivial base 1 modulo n. For more information (n = 201 to 5000), see b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) (Table of pseudoprimes 16–4999).
Unlike the list above, that page excludes the bases 1 and n−1.
[10] For example, the smallest even weak pseudoprime to base 2 is 161038 (see OEIS: A006935).
The least weak pseudoprime to bases b = 1, 2, ... are: Carmichael numbers are weak pseudoprimes to all bases, thus all terms in this list are less than or equal to the smallest Carmichael number, 561.
The least Fermat pseudoprime to base b (also not necessary exceeding b) (OEIS: A090086) is usually semiprime, but not always; the first counterexample is A090086(648) = 385 = 5 × 7 × 11.
Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure.
The rarity of such pseudoprimes has important practical implications.
For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes.
The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality.
If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test.