Fermat witnesses and liars (some words on PWW #24)

Let $n$ be a positive integer we want to test for primality, and suppose $a$ is some other positive integer with $a < n$ . There are then four possibilities:

$a$ and $n$ could share a common factor. In this case we can find the common factor using the Euclidean Algorithm, and $n$ is definitely not prime. (See my previous post.)
On the other hand, $a$ and $n$ might not share a prime factor, that is, they might be relatively prime (or put yet another way, their GCD might be $1$ ). This case breaks down into three subcases:
- $a^{n-1} \not \equiv 1 \pmod n$ . In this case we know by (the contrapositive of) Fermat’s Little Theorem that $n$ is definitely composite (although we don’t learn anything about its factorization); $a$ is called a Fermat witness for $n$ .
- $n$ is prime. In this case, Fermat’s Little Theorem tells us that $a^{n-1}$ must be equivalent to $1$ modulo $n$ . However, computing $a^{n-1}$ doesn’t necessarily tell us much, because the next case is also possible:
- $a^{n-1} \equiv 1 \pmod n$ but $n$ is composite. In this case $a$ is called a Fermat liar for $n$ .

The question becomes: for a given composite $n$ , how many Fermat liars and Fermat witnesses could there be? How many values of $a$ do we have to test to be “reasonably sure” whether $a$ is prime or composite?

Each pixel in the image from my previous post represents a particular $(a,n)$ pair. Each row represents a value of $n$ , with the top row corresponding to $n = 2$ and the bottom row to $n = 600$ . Each column represents a value of $a$ . Of course we only consider pairs $(a,n)$ with $a \leq n$ , which explains the triangular shape. (I include the case $a = n$ to complete the triangle, although these are not interesting from a primality testing point of view.)

The four cases outlined above correspond to the four colors:

If $a$ and $n$ share a common factor, the pixel is colored yellow.
If $a$ is a Fermat witness for $n$ , the pixel is green.
If $n$ is prime, the pixel is blue.
If $a$ is a Fermat liar for $n$ , the pixel is red.

Here’s a much smaller sample of the same visualization so we can see more clearly what’s going on.

Primes of course yield blue stripes. Non-primes are stripes of yellow, green, and sometimes red. Testing a particular $n$ to see whether it is prime corresponds to picking random squares from its row: if we hit a yellow or green square, we learn immediately that $n$ is composite. If we hit a red square or a blue square, we aren’t sure. So far, however, things don’t look too bad: there are only a few isolated red squares, so picking two or three random values should be enough to ensure that we either find out $n$ is composite, or can safely assume that it is prime. Let’s continue the picture a bit farther; here are the first 100 values of $n$ :

I’ve also included some purple bars to the left of each row, showing what proportion of the numbers relatively prime to $n$ are Fermat liars. So far, none of the purple bars extend beyond the halfway mark (the first vertical line corresponds to half, and the second, slightly darker vertical line corresponds to $1$ ). It turns out there’s a good reason for this:

Theorem: if $n$ is composite and there exists at least one Fermat witness for $n$ , then at least half of the numbers relatively prime to $n$ are Fermat witnesses.

Some questions for you:

Can you prove this? The proof is not hard given the right idea.
Suppose that for every composite $n$ , at least half the relatively prime values of $a$ are Fermat witnesses. If we pick $k$ random values of $a < n$ and find that $a^{n-1} \equiv 1 \pmod n$ for all of them, what can we say about the probability that $n$ is prime?
The theorem has that pesky condition, “if there exists at least one Fermat witness for $n$ ”… do you think there could be composite values of $n$ with no Fermat witnesses? (Hint: go back and look at the picture from my previous post…)

About Brent

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

View all posts by Brent →