Monday Math: Fermat's Little Theorem

The big number theory course has moved on to modular arithmetic, which means we have been discussing Fermat's Little Theorem. Personally I've always thought that name is just adorable. As it happens, I already did a post on this topic. But since that post is close to a year old, and since I did not have my funky TeX renderer installed then, how about I repost it. Enjoy!

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:

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

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

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

This time we get

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

That is equivalent to showing that the fraction

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 the same color. Subtracting this from our total gives us

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:

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

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

If we shift everything once we get

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

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

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.