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 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. 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. It follows that if x is a Fermat pseudoprime to base a, then x is coprime to a.

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 Poulet numbers, after the Belgian mathematician Paul Poulet, Sarrus numbers, or Fermatians (sequence 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.

The definition is trivially met if a ≡ ±1 mod n so these trivial bases are often excluded.

Some sources use variations of the definition, for example to only allow odd numbers to be pseudoprimes.

Every odd number q satisfies ${\displaystyle a^{q-1}\equiv 1{\pmod {q}}}$ for ${\displaystyle a=q-1}$. This trivial case is excluded in the definition of a Fermat pseudoprime given by Crandall and Pomerance:

...
Wikipedia