## Making the Fermat primality test deterministic

Let’s recall Fermat’s Little Theorem:

If $p$ is prime and $a$ is an integer where $0 < a < p$, then $a^{p-1} \equiv 1 \pmod p$.

Recall that we can turn this directly into a test for primality, called the Fermat primality test, as follows: given some number $n$ that we want to test for primality, pick an integer $a$ between $0$ and $n$ (say, at random), and compute $a^{n-1} \pmod n$. If the result is not equal to $1$, then Fermat’s Little Theorem tells us that $n$ is definitely not prime. Repeat some fixed number of times $k$. If we get $1$ every time, then report that $n$ is probably prime.

## Making Fermat Deterministic

This “probably prime” business is a little annoying. Can we somehow turn this into a deterministic primality test? Well, for one thing, instead of just picking $k$ random values, what if we tested all $1 < a < n-1$? (Yes, of course this would take way too long, but bear with me for a bit!) If they all yield $1 \pmod n$ when raised to the $(n-1)$ power, could $n$ still possibly be composite, or could we conclude it is definitely prime? Put another way, are there any composite numbers $n$ such that $a^{n-1} \equiv 1 \pmod n$ for all $0 < a < p$?

It turns out that this would work: there do not exist composite numbers such that $a^{n-1} \equiv 1 \pmod n$ for all $0 < a < p$, so if we test all possible values of $a$ and we always get $1$, then we can conclude with certainty that $n$ is prime. Let’s prove it!

Suppose $n$ is composite, and let $0 < a < p$ be some number which shares a nontrivial common divisor $g$ with $n$, that is, $g = \gcd(a,n) \neq 1$. If $n$ is composite then such an $a$ must exist; for example, we could just take $a$ to be one of $n$’s prime divisors. Now, I claim that $a^{n-1}$ can’t possibly be equivalent to $1 \pmod n$. Let $r$ be the remainder when dividing $a^{n-1}$ by $n$, that is, $a^{n-1} \equiv r \pmod n$. Rearranging gives $a^{n-1} - r \equiv 0 \pmod n$, which means that $a^{n-1} - r$ is divisible by $n$, that is, $a^{n-1} - r = qn$ for some integer $q$. Rearranging this again, we get $a^{n-1} - qn = r$. But by our assumption, $n$ and $a$ are both divisible by $g$, and hence $a^{n-1} - qn$ must be divisible by $g$—but that means $r$ must be divisible by $g$ as well. Since we assumed that $a$ and $n$ have a nontrivial common factor, that is, $g \neq 1$, we conclude that $r \neq 1$ too, that is, $a^{n-1} \not\equiv 1 \pmod n$.

So we now know that any number $a$ which shares a common factor with $n$ will definitely reveal the fact that $n$ is composite. How many (or how few) such $a$ could there be? And what about other values of $a$, which don’t share a factor with $n$—how many of them might also reveal the fact that $n$ is composite? We’ll tackle these questions in my next post! 