Let’s recall Fermat’s Little Theorem:
If is prime and is an integer where , then .
Recall that we can turn this directly into a test for primality, called the Fermat primality test, as follows: given some number that we want to test for primality, pick an integer between and (say, at random), and compute . If the result is not equal to , then Fermat’s Little Theorem tells us that is definitely not prime. Repeat some fixed number of times . If we get every time, then report that 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 random values, what if we tested all ? (Yes, of course this would take way too long, but bear with me for a bit!) If they all yield when raised to the power, could still possibly be composite, or could we conclude it is definitely prime? Put another way, are there any composite numbers such that for all ?
It turns out that this would work: there do not exist composite numbers such that for all , so if we test all possible values of and we always get , then we can conclude with certainty that is prime. Let’s prove it!
Suppose is composite, and let be some number which shares a nontrivial common divisor with , that is, . If is composite then such an must exist; for example, we could just take to be one of ’s prime divisors. Now, I claim that can’t possibly be equivalent to . Let be the remainder when dividing by , that is, . Rearranging gives , which means that is divisible by , that is, for some integer . Rearranging this again, we get . But by our assumption, and are both divisible by , and hence must be divisible by —but that means must be divisible by as well. Since we assumed that and have a nontrivial common factor, that is, , we conclude that too, that is, .
So we now know that any number which shares a common factor with will definitely reveal the fact that is composite. How many (or how few) such could there be? And what about other values of , which don’t share a factor with —how many of them might also reveal the fact that is composite? We’ll tackle these questions in my next post!