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!

Pingback: The Fermat primality test and the GCD test | The Math Less Traveled