Fermat primality test

Summary

The Fermat primality test is a probabilistic test of whether an integer $n > 1$ is prime. It chooses a base $a$ with $1 < a < n - 1$ and computes $a^{n-1} \bmod n$ by modular exponentiation. If the result is not $1$, then $n$ is composite, by Fermat's little theorem. If the result is $1$, then $n$ is called a probable prime to the base $a$.

Remarks

A probable prime can be composite. Such a number is a Fermat pseudoprime. The Carmichael numbers pass the test for each base coprime to them. So repeated tests with many bases cannot detect all composite numbers. The Miller–Rabin primality test is a stronger test of the same kind, without this weakness.

Explanations

L1 human

To test $n = 15$ with $a = 2$, compute $2^{14} = 16384 \equiv 4 \pmod{15}$. The result is not $1$, so $15$ is surely composite. The test does not find a factor; it only proves that one exists.