Making the Fermat primality test deterministic

Let’s recall Fermat’s Little Theorem:

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

Recall that we can turn this directly into a test for primality, called the Fermat primality test, as follows: given some number n that we want to test for primality, pick an integer a between 0 and n (say, at random), and compute a^{n-1} \pmod n. If the result is not equal to 1, then Fermat’s Little Theorem tells us that n is definitely not prime. Repeat some fixed number of times k. If we get 1 every time, then report that n 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 k random values, what if we tested all 1 < a < n-1? (Yes, of course this would take way too long, but bear with me for a bit!) If they all yield 1 \pmod n when raised to the (n-1) power, could n still possibly be composite, or could we conclude it is definitely prime? Put another way, are there any composite numbers n such that a^{n-1} \equiv 1 \pmod n for all 0 < a < p?

It turns out that this would work: there do not exist composite numbers such that a^{n-1} \equiv 1 \pmod n for all 0 < a < p, so if we test all possible values of a and we always get 1, then we can conclude with certainty that n is prime. Let’s prove it!

Suppose n is composite, and let 0 < a < p be some number which shares a nontrivial common divisor g with n, that is, g = \gcd(a,n) \neq 1. If n is composite then such an a must exist; for example, we could just take a to be one of n’s prime divisors. Now, I claim that a^{n-1} can’t possibly be equivalent to 1 \pmod n. Let r be the remainder when dividing a^{n-1} by n, that is, a^{n-1} \equiv r \pmod n. Rearranging gives a^{n-1} - r \equiv 0 \pmod n, which means that a^{n-1} - r is divisible by n, that is, a^{n-1} - r = qn for some integer q. Rearranging this again, we get a^{n-1} - qn = r. But by our assumption, n and a are both divisible by g, and hence a^{n-1} - qn must be divisible by g—but that means r must be divisible by g as well. Since we assumed that a and n have a nontrivial common factor, that is, g \neq 1, we conclude that r \neq 1 too, that is, a^{n-1} \not\equiv 1 \pmod n.

So we now know that any number a which shares a common factor with n will definitely reveal the fact that n is composite. How many (or how few) such a could there be? And what about other values of a, which don’t share a factor with n—how many of them might also reveal the fact that n is composite? We’ll tackle these questions in my next post!

About Brent

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.

1 Response to Making the Fermat primality test deterministic

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

Comments are closed.