Carmichael number

Definition

A Carmichael number is a composite number $n$ such that $a^{n-1} \equiv 1 \pmod n$ for each integer $a$ coprime to $n$.

Remarks

Thus a Carmichael number is a Fermat pseudoprime to each base coprime to it. Korselt's criterion: a composite $n$ is a Carmichael number if and only if $n$ is square-free and $p - 1 \mid n - 1$ for each prime $p \mid n$. The smallest Carmichael number is $561 = 3 \cdot 11 \cdot 17$. Here $2$, $10$ and $16$ divide $560$. Alford, Granville and Pomerance proved in 1994 that there are infinitely many Carmichael numbers.

Explanations

L1 human

A Carmichael number behaves like a prime for the Fermat test, for each base that has no common factor with it. So the Fermat primality test cannot detect it, unless the base shares a factor with it.