Fermat’s Little Theorem

Thankfully, there are good Monte Carlo algorithms for primality testing. A number of them revolve around a theorem first published back in the year 1640.

Pierre de Fermat, a 17th-century French mathematician, came up with a number of mathematical theorems in his lifetime, and the one relevant to us is known as Fermat’s Little Theorem. (Yes, it’s actually called that, and don’t ask me why.)

Fermat’s Little Theorem can be expressed in a number of ways, but I’ll present it in the way that I feel is clearest for our context. Here goes.

Let’s use the variable N to refer to a number we’re testing for being prime. Every number N has a series of smaller numbers that run from 1 up to N, excluding N itself. We’re going to use another variable, A, to refer to these smaller numbers.

Now, it may sound strange that a single variable can refer to a bunch of numbers, but here’s what I mean. If N is 7, the numbers 1, 2, 3, 4, 5, and 6 all qualify as A. So, if we have a formula that contains our A variable, we can plug any one of the numbers from 1 through 6 into A that we’d like; it’s our choice. This will become clearer in a moment.

Fermat’s Little Theorem is that if N is prime, then the following formula (expressed in Python code) will be true for all possible numbers that we can plug into A:

This expression states that if we take a number A, raise it to the power of N - 1, and then divide the result by N, we’ll get a remainder of 1.

In other words, what Fermat’s Little Theorem is saying is: if N is prime, then all possibilities of A will plug into this formula and produce a result of 1.

This may sound confusing, I know. So, let me clarify this theorem with an example. For the rest of this chapter, I’m going to refer to A**(N-1) % N as “The Formula.” (It’s way easier to type.)

Let’s say that N is 7, which is prime. The list, A, as mentioned, includes the numbers 1, 2, 3, 4, 5, and 6. If we take any number from A, say the number 3, and apply The Formula, we get:

As you can see, this computes to 1.

Fermat’s Little Theorem says that The Formula will compute to 1 for all integers that qualify as A. To demonstrate, all of the following statements are true:

You have to admit that this is pretty cool. We’re not going to look at why this is so, but let’s run with it.

To recap, Fermat’s Little Theorem claims that if N is prime, then for all of A (which are the numbers from 1 up until N, not including N), if we compute The Formula, we’ll get the result of 1.

Now, the following statement is key, so listen up and listen well.

A logical equivalence of Fermat’s Little Theorem is that if we compute The Formula and get a result that is not 1, then we know that N is composite. This follows logically, for if we’re guaranteed that for a prime N that The Formula will produce 1, that means if we don’t get a result of 1, then N cannot possibly be prime.

What Fermat’s Little Theorem does not mean, though, is that if we do get 1, then N is prime. Many composite numbers have at least one number A in which The Formula will produce 1. All Fermat said was that if N is prime, then The Formula will produce 1 for every A. And equivalently, if The Formula does not produce 1 for any given A, then we know that N is composite.

It turns out that Fermat’s Little Theorem is a one-directional rule. We can use it to prove whether a given number is composite, but cannot use it to prove whether the number is prime.

In any case, now that we’re armed with Fermat’s Little Theorem, we’re ready to discover a good Monte Carlo primality test.