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$.