Making the Fermat primality test deterministic

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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →