Fermat primality test

Definition

The Fermat primality test is a quick and often inconclusive primality test. In the version below, we consider only $n>1$.

Given a natural number $n>1$, the test works as follows:

1. Pick a random element $a$ from the congruence classes of nonzero integers mod $n$ (exclude the congruence class of 0). Explicitly, pick $a$ as an integer among $1,2,3,\dots ,n-1$.
2. Check whether $a^{n-1}\equiv 1(\mathrm{mod}n)$. To compute the power use repeated squaring. If the condition does not hold, then $n$ is composite. If the condition does hold, then $n$ may be prime or composite.

The above is a single iteration of the test. Multiple iterations of the test may be carried out with multiple random elements. If at any stage the condition $a^{n-1}\equiv 1(\mathrm{mod}n)$ is violated, we can conclude that the number is composite. If, however, the condition holds every time, the situation is inconclusive and $n$ may be prime or composite.

Theory

Why it works

The primality test above is correct because of Fermat's little theorem, which says that for a prime $p$ and $a$ relatively prime to $p$, we have:

$a^{p-1}\equiv 1(\mathrm{mod}p)$

Behavior on composite numbers

For any composite number $n$, we use the following terms:

• A Fermat witness for $n$ is a value $a$ such that $a^{n-1}\equiv ̸1(\mathrm{mod}n)$.
• A Fermat liar for $n$ is a value $a$ such that $a^{n-1}\equiv 1(\mathrm{mod}n)$.
• We say that $n$ is a Fermat pseudoprime to base $a$ if $a$ is a Fermat liar for $n$.

Nonzero numbers that have a common factor with $n$ always serve as Fermat witnesses. There are $n-\phi (n)-1$ of these where $\phi$ is the Euler totient function. For $n$ composite, this number is at least equal to $\sqrt{n}-1$, the worst case arising when $n$ is a square of a prime. In general, if $n$ has a small number of large prime factors, there are very few such numbers and a uniform random choice is highly unlikely to hit them.

For the numbers that are relatively prime to $n$, we have the formula for probability of relatively prime integer being a Fermat liar. If the probability is 1, then $n$ is a Carmichael number. If the probability is less than 1, then it is at most 1/2, which means that the Fermat primality test can find a witness with arbitrarily high probability of success in a finite number of trials.

Related tests

• Miller-Rabin primality test
• Solovay-Strassen primality test