Fermat pseudoprime

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 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. 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 p be any odd prime that does not divide a2 - 1. Let A = (ap - 1)/(a - 1) and let B = (ap + 1)/(a + 1). 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 ).