## The Fermat primality test

After several long tangents writing about orthogons and the chromatic number of the plane, I’m finally getting back to writing about primality testing. All along in this series, my ultimate goal has been to present some general primality testing algorithms and the math behind them, and now we’re finally ready to see our first (sort of!). As a reminder, and as a guide for anyone reading this without reading the previous posts, here’s the story so far:

• We first saw three different versions of Fermat’s Little Theorem (FlT), as well as a statement of Euler’s Theorem which is a generalization of FlT. Don’t worry if you don’t remember what Fermat’s Little Theorem says; I’ll remind you below. (As an aside, I recently learned there is yet a further generalization of Euler’s Theorem called Carmichael’s Theorem, but that will have to be another post for another time!)
• Just for fun, we saw three differenet proofs of FlT: by modular arithmetic, by combinatorics, and by group theory, as well as corresponding proofs of Euler’s Theorem.
• We then talked about three hypothetical machines for determining properties of a natural number $n$: one to give the complete prime factorization, one to give a single factor, and one to say whether $n$ is prime. I also mentioned the (surprising) fact that it is possible to build relatively fast machines of the third type—that is, for doing primality testing—but as far as we know, any machines to find factors are much slower.
• Finally, we talked about what we really mean by “fast” and “slow” in the description above.

So let’s see our first primality testing machine! This one is actually very simple. Remember that Fermat’s Little Theorem (the first version) says:

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

We can turn this directly into a test for primality, as follows: given some number $n$ that we want to test for primality, pick an integer $a$ between $0$ and $n$ (say, randomly), and compute $a^{n-1} \pmod n$. If the result is not equal to $1$, then $n$ is definitely not prime, since it would contradict Fermat’s Little Theorem. In that case we can immediately stop and report that $n$ is composite (though note that we have not found any factors!).

(In actual practice, we don’t bother trying $a = 1$ or $a = n-1$; we only pick from $1 < a < n-1$. Can you see why it’s useless to test $a = 1$ or $a = n-1$?)

For example, suppose we want to test $n = 8$. Let’s pick $a = 2$. We compute $a^{n-1} = 2^7 = 128 \equiv 0 \pmod 8$; hence $n = 8$ is not prime (but you probably knew that already). In this particular exampe $a$ is actually a factor of $n$, but it need not be. For example, let $n = 15$ and pick $a = 7$; then computing $7^{14} \equiv 4 \pmod {15}$ proves that $n$ is composite, even though $7$ and $15$ share no common factors.

So what if $a^{n-1}$ is equivalent to $1 \pmod n$? Unfortunately, Fermat’s Little Theorem is not an “if and only if” statement! It is quite possible to have $a^{n-1} \equiv 1 \pmod n$ even when $n$ is composite. So if we do get a result of $1$, we simply can’t conclude anything about $n$. For example, with $n = 15$ again, if we happened to pick $a = 4$ instead of $a = 7$, then we get $4^{14} \equiv 1 \pmod {15}$ even though $15$ isn’t prime.

So suppose we pick some $a$ and get $a^{n-1} \equiv 1 \pmod n$. What can we do? Well, just try another $a$! If we get $a^{n-1} \not\equiv 1 \pmod n$ for the new $a$, stop and report that $n$ is composite. Otherwise, pick another $a$, and so on.

In general, we can iterate some fixed number of times $k$. If we ever find an $a$ such that $a^{n-1} \not\equiv 1 \pmod n$, then we can report that $n$ is definitely not prime. Otherwise, if we get through testing $k$ different values of $a$ and they all yield $1$, then we can report that $n$ is probably prime.

So this is better than nothing, but it’s not quite a primality machine, because it can’t tell us for sure that a number is prime. And it leaves a lot more questions: could we make $k$ big enough so that we could know for sure whether $n$ is prime? How big would $k$ have to be? What about for composite numbers; how fast do we expect this to be? Are there other ways to build on this basic idea to get better (faster, more certain) primality tests? I’ll write about all this and more in future posts! Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in computation, number theory, primes and tagged , , . Bookmark the permalink.

### 5 Responses to The Fermat primality test

1. Mark James says:

You also need to be careful about Carmichael numbers. (https://en.wikipedia.org/wiki/Carmichael_number)

For example, 561 will pass the FLT test a little more than 50% of the time.

• Brent says:

Indeed! I plan to write about those next time.