Let be a positive integer we want to test for primality, and suppose is some other positive integer with . There are then four possibilities:
and could share a common factor. In this case we can find the common factor using the Euclidean Algorithm, and is definitely not prime. (See my previous post.)
On the other hand, and might not share a prime factor, that is, they might be relatively prime (or put yet another way, their GCD might be ). This case breaks down into three subcases:
- . In this case we know by (the contrapositive of) Fermat’s Little Theorem that is definitely composite (although we don’t learn anything about its factorization); is called a Fermat witness for .
- is prime. In this case, Fermat’s Little Theorem tells us that must be equivalent to modulo . However, computing doesn’t necessarily tell us much, because the next case is also possible:
- but is composite. In this case is called a Fermat liar for .
The question becomes: for a given composite , how many Fermat liars and Fermat witnesses could there be? How many values of do we have to test to be “reasonably sure” whether is prime or composite?
Each pixel in the image from my previous post represents a particular pair. Each row represents a value of , with the top row corresponding to and the bottom row to . Each column represents a value of . Of course we only consider pairs with , which explains the triangular shape. (I include the case 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 and share a common factor, the pixel is colored yellow.
- If is a Fermat witness for , the pixel is green.
- If is prime, the pixel is blue.
- If is a Fermat liar for , 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 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 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 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 :
I’ve also included some purple bars to the left of each row, showing what proportion of the numbers relatively prime to 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 ). It turns out there’s a good reason for this:
Theorem: if is composite and there exists at least one Fermat witness for , then at least half of the numbers relatively prime to 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 , at least half the relatively prime values of are Fermat witnesses. If we pick random values of and find that for all of them, what can we say about the probability that is prime?
- The theorem has that pesky condition, “if there exists at least one Fermat witness for ”… do you think there could be composite values of with no Fermat witnesses? (Hint: go back and look at the picture from my previous post…)