# 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\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ and $b\not\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$, then $n$ is composite. The Fermat compositeness test consists of checking whether ${b}^{n-1}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ for a handful of values of $b$. If a $b$ with ${b}^{n-1}\not\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ is found, then $n$ is composite.

A value of $b$ for which ${b}^{n-1}\not\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ is called a *witness* to $n$’s compositeness. If ${b}^{n-1}\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(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).

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 |