## You are here

HomeFermat compositeness test

## Primary tabs

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

A value of $b$ for which $b^{{n-1}}\not\equiv 1\;\;(\mathop{{\rm mod}}n)$ is called a *witness* to $n$’s compositeness. If $b^{{n-1}}\equiv 1\;\;(\mathop{{\rm mod}}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).

## Mathematics Subject Classification

11A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections