# 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\pmod{n}$ and $b\not\equiv 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}\not\equiv 1\pmod{n}$ is found, then $n$ is composite.

A value of $b$ for which $b^{n-1}\not\equiv 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 http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002997A002997 for a list of first few Carmichael numbers).

Title Fermat compositeness test FermatCompositenessTest 2013-03-22 13:17:36 2013-03-22 13:17:36 bbukh (348) bbukh (348) 15 bbukh (348) Algorithm msc 11A51 MillerRabinPrimeTest pseudoprime witness Carmichael numbers