Fermat pseudoprime

Definition

Let $a$ be an integer with $a > 1$. A Fermat pseudoprime to the base $a$ is a composite number $n$ such that $a^{n-1} \equiv 1 \pmod n$.

Remarks

Fermat's little theorem says that each prime $n$ with $n \nmid a$ satisfies $a^{n-1} \equiv 1 \pmod n$. A Fermat pseudoprime is a composite number that passes the same test. The smallest Fermat pseudoprime to the base $2$ is $341 = 11 \cdot 31$. The condition implies $\gcd(a, n) = 1$. A composite number that is a Fermat pseudoprime to each base coprime to it is a Carmichael number.

Explanations

L1 human

The Fermat primality test declares $n$ "probably prime" when $a^{n-1} \equiv 1 \pmod n$. A Fermat pseudoprime is a composite number that fools this test for the base $a$. For example, $2^{340} \equiv 1 \pmod{341}$, but $341$ is not prime.