Fermat pseudoprime

Fermat's little theorem states that if p is prime and a is coprime to p, then a^p−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides a^x−1 − 1, then x is called a Fermat pseudoprime to base a. [1]^{: Def. 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.

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: 2³⁴⁰ ≡ 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).

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.[2][1]^{: Def. 3.34}

If composite ${\displaystyle n}$ is even, then ${\displaystyle n}$ is a Fermat pseudoprime to the trivial base ${\displaystyle b\equiv 1{\pmod {n}}}$. If composite ${\displaystyle n}$ is odd, then ${\displaystyle n}$ is a Fermat pseudoprime to the trivial bases ${\displaystyle b\equiv \pm 1{\pmod {n}}}$.

For any composite ${\displaystyle n}$, the number of distinct bases ${\displaystyle b}$ modulo ${\displaystyle n}$, for which ${\displaystyle n}$ is a Fermat pseudoprime base ${\displaystyle b}$, is [7]^{: Thm. 1, p. 1392}

${\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}$

where ${\displaystyle p_{1},\dots ,p_{k}}$ are the distinct prime factors of ${\displaystyle n}$. This includes the trivial bases.

For example, for ${\displaystyle n=341=11\cdot 31}$, this product is ${\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}$. For ${\displaystyle n=341}$, the smallest such nontrivial base is ${\displaystyle b=2}$.

Every odd composite ${\displaystyle n}$ is a Fermat pseudoprime to at least two nontrivial bases modulo ${\displaystyle n}$ unless ${\displaystyle n}$ is a power of 3.[7]^{: Cor. 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,[8] this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n). When p is a prime, p² is a Fermat pseudoprime to base b if and only if p is a Wieferich prime to base b. For example, 1093² = 1194649 is a Fermat pseudoprime to base 2, and 11² = 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, ... (sequence A063994 in the OEIS)

The least base b > 1 which n is a pseudoprime to base b (or prime number) are

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (sequence A105222 in the OEIS)

The number of the values of b for n must divides ${\displaystyle \varphi }$(n), or A000010(n) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... (The quotient can be any natural number, and the quotient = 1 if and only if n is a prime or a Carmichael number (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997), the quotient = 2 if and only if n is in the sequence: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311)

The least number with n values of b are (or 0 if no such number exists)

1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (sequence A064234 in the OEIS) (if and only if n is even and not totient of squarefree number, then the nth term of this sequence is 0)

A composite number n which satisfy that ${\displaystyle b^{n}\equiv b{\pmod {n}}}$ is called weak pseudoprime to base b. A pseudoprime to base a (under the usual definition) satisfies this condition. Conversely, a weak pseudoprime that is coprime with the base is a pseudoprime in the usual sense, otherwise this may or may not be the case.[9] The least weak pseudoprime to base b = 1, 2, ... are:

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... (sequence A000790 in the OEIS)

All terms are less than or equal to the smallest Carmichael number, 561. Except for 561, only semiprimes can occur in the above sequence, but not all semiprimes less than 561 occur, a semiprime pq (p ≤ q) less than 561 occurs in the above sequences if and only if p − 1 divides q − 1. (see OEIS: A108574) Besides, the smallest pseudoprime to base n (also not necessary exceeding n) (OEIS: A090086) is also usually semiprime, the first counterexample is A090086(648) = 385 = 5 × 7 × 11.

If we require n > b, they are (for b = 1, 2, ...)

4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... (sequence A239293 in the OEIS)

Carmichael numbers are weak pseudoprimes to all bases.

The smallest even weak pseudoprime in base 2 is 161038 (see OEIS: A006935).

Another approach is to use more refined notions of pseudoprimality, e.g. strong pseudoprimes or Euler–Jacobi pseudoprimes, for which there are no analogues of Carmichael numbers. This leads to probabilistic algorithms such as the Solovay–Strassen primality test, the Baillie–PSW primality test, and the Miller–Rabin primality test, which produce what are known as industrial-grade primes. 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. However, deterministic primality tests are slow. 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.

• W. F. Galway and Jan Feitsma, Tables of pseudoprimes to base 2 and related data (comprehensive list of all pseudoprimes to base 2 below 2⁶⁴, including factorization, strong pseudoprimes, and Carmichael numbers)
• A research for pseudoprime