Fermat compositeness test

The Fermat compositeness test is a primality test based on the observation that by Fermat’s little theorem if $b^{n-1}\not\equiv 1(modn)$ and $b\not\equiv 0(modn)$, then $n$ is composite. The Fermat compositeness test consists of checking whether $b^{n-1}\equiv 1(modn)$ for a handful of values of $b$. If a $b$ with $b^{n-1}\not\equiv 1(modn)$ is found, then $n$ is composite.

A value of $b$ for which $b^{n-1}\not\equiv 1(modn)$ is called a witness to $n$’s compositeness. If $b^{n-1}\equiv 1(modn)$, then $n$ is said to be pseudoprime base $b$.

It can be proven that most composite numbers can be shown to be composite by testing only a few values of $b$. However, there are infinitely many composite numbers that are pseudoprime in every base. These are Carmichael numbers (see OEIS sequence http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002997A002997 for a list of first few Carmichael numbers).