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
Canonical name	FermatCompositenessTest
Date of creation	2013-03-22 13:17:36
Last modified on	2013-03-22 13:17:36
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	15
Author	bbukh (348)
Entry type	Algorithm
Classification	msc 11A51
Related topic	MillerRabinPrimeTest
Defines	pseudoprime
Defines	witness
Defines	Carmichael numbers