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} \nequiv 1\pmod n$ and $b\nequiv 0\pmod n$ , then $n$ is composite. The Fermat compositeness test consists of checking whether $b^{n-1} \equiv 1\pmod n$ for a handful of values of $b$ . If a $b$ with $b^{n-1} \nequiv 1\pmod n$ is found, then $n$ is composite.

A value of $b$ for which $b^{n-1} \nequiv 1\pmod n$ is called a witness to $n$ 's compositeness. If $b^{n-1} \equiv 1\pmod n$ , 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 A002997 for a list of first few Carmichael numbers).