A Combinatorial Proof of Fermat's Little Theorem

I learned something new the other day while preparing for my History of Math class. And since I have not done a math post in a while, I thought I would tell you about it. Specifically, I learned a new, and very clever, method for proving Fermat's Little Theorem.

Fermat's Little Theorem is a classic result from elementary number theory, first stated by Fermat but first proved by Euler. It can be stated in a number of different ways, but here is the version most useful for what I am about to do:

Let k be a positive integer and let p be a prime number. Then k^p - k is a multiple of p.



This is commonly referred to as ``Fermat's Little Theorem,'' presumably to distinguish it from his more famous Last Theorem.

Let us consider some examples. Let us take 3 as our prime number. For k, let us try the numbers 2, 4 and 5. We get

2³ - 2 = 8 - 2 = 6

which is a multiple of three. With 4 and 5 we get

4³ - 4 = 64 - 4 = 60 and 5³ - 5 = 125 - 5 = 120

which gives us two more multiples of three. Notice that I did not test the numbers k = 3 or k = 6, because in these cases it is obvious without doing the calculation that the result will be a multiple of three. If k is a multiple of three to begin with, then it is clear that k^p - k will also be a multiple of three.

Let us try one more example. Take p = 11 and k = 7. This time we get

7¹¹ - 7 = 1,977,326,743 - 7 = 1,977,326,736



which I think you will find is a multiple of eleven.

You might be wondering at this point why anyone would care about such a result. Of course, it reflects very badly on you that you would wonder about such things. Still, it is an amusing fact that Fermat's Little Theorem has a role to play in RSA Cryptography.

There are many ways of proving the theorem, but I shall just present one. It is based on a simple counting argument. We want to show that k^p - k is a multiple of p. That is equivalent to showing that the result of dividing k^p - k by p is an integer. We will show this by establishing that this fraction is equal to the number of elements in a particular set, and therefore must be an integer. Here we go!

Suppose you have beads that come in k colors. You are going to select p of these beads to arrange along a string. It is perfectly acceptable to repeat colors. Since we are using p beads, and each of them can be in any of k colors, we see that there are k^p different color sequences.

Since it is boring to have all the beads be of the same color, we will require that at least two colors be used. There are k strings in which all of the beads are of the same color. Subtracting this from our total gives us k^p - k many strings in which at least two different colors are used.

Now we will tie together the ends of the string to form a bracelet. When this happens some of our strings become indistinguishable. For example, suppose we were only using three beads. When we lay them on the straight line on a table, the string Green, Blue, Orange would look different from the string Blue, Orange, Green. But if we tie the ends together the two bracelets would be indistinguishable.

We now ask, “Of the k^p - k many bracelets using at least two colors, how many of them are distinguishable from one another?” The answer is that each string of p beads can be shifted cyclically without producing a different bracelet. In our example, the strings:

Green, Blue, Orange   and   Blue, Orange, Green   and   Orange, Green, Blue



will all look like the same bracelet when the ends are tied together. Since each of the p cyclic shifts of a given color string will lead to indistinguishable bracelets, we see that the number of indistinguishable bracelets using at least two colors is given by k^p - k divided by p. And since the number of such bracelets is plainly an integer, our proof is complete.

Very cool. Combinatorial proofs are always very pretty.

You might be wondering where in that argument we used the assumption that p was a prime number. It came in the step where we asserted that each color string gets counted p different times, once for each of the possible cyclic shifts. That is true for a prime number, but is not true in general. For example, suppose we are using six beads and we begin with the string

Green, Blue, Blue, Green, Blue, Blue



If we shift everything once we get

Blue, Blue, Green, Blue, Blue, Green



which will lead to an identical bracelet. One more shift gives us

Blue, Green, Blue, Blue, Green, Blue



which is yet another version of the same bracelet. But one more shift brings us to

Green, Blue, Blue, Green, Blue, Blue



which is precisely the one we started with. In this case there are only three color strings that lead to bracelets indistinguishable from the original one.

This is precisely the sort of thing that can not happen if you are using a prime number of beads. Since nothing divides a prime evenly, you can not have a repeating pattern like the one we just saw.