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 kp - 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


23 - 2 = 8 - 2 = 6

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

43 - 4 = 64 - 4 = 60 and 53 - 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


711 - 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 kp - k is a multiple of p. That is equivalent to showing that the result of dividing kp - 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 kp 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 kp - 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 kp - 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 kp - 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.

More like this

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…
In my last math post I casually mentioned that the sum of the reciprocals of the primes diverges. That is \[ \frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+\frac{1}{13}+ \dots=\infty \]   That seems like a hard thing to prove. Certainly none of the traditional convergence tests…
When I was about twelve years old, I came up with an idea for a massive practical joke to play on an unsuspecting baby. For its entire childhood, everyone around the baby would conspire to convince it that the sky was green. Then at some point in the future, perhaps in front of the entire sixth…
A continuation of our "greatest hits" from past Cognitive Daily postings: [originally posted on September 27, 2005] All this talk about stereotypes can get you thinking. Perhaps some stereotypes reflect actual differences. Take color vision, for example: men often refer to themselves as "color-…

If you lift the bracelet off the workspace, you get another symmetry by flipping the bracelet over. This way, Blue Orange Green ~ Green Orange Blue, so you can actually divide by 2p. You can see that k^p-k must be even by working out the cases for k/p each even/odd.

On further inspection, I have found this is in Golomb's paper (http://www.cimat.mx/~mmoreno/teaching/spring08/Fermats_Little_Thm.pdf). It won't work for p=2, which makes sense.

Nice!

By Kameron Decker… (not verified) on 15 Apr 2010 #permalink

Hmm.

So THAT's how much wood a woodchuck could chuck then?

By pboyfloyd (not verified) on 16 Apr 2010 #permalink

There's a similar-in-spirit proof of Cauchy's theorem that for any prime p every group whose order is a multiple of p has an element of order p: consider p-tuples of elements whose product is 1; the set of all these is invariant under cyclic permutation; p-tuples whose elements aren't all equal give you orbits of size p when you do this, so the total number of such p-tuples in the set is a multiple of p (*); so is the total number altogether (because it's |G|^(p-1)); so the number of elements with x^p=1 is a multiple of p; and that number isn't 0 because the identity is such an element.

The observation I labelled with "(*)" is pretty much the exact same thing as the one that makes the FLittleT proof work.

I know you mathematicians are into mathematical proofs, which are beyond my expertise or interest, but of course this is a dimensional problem, and you cannot express something with fewer variables than dimensions. That is my proof. Let you mathematicians waste more centuries on this. Given that this is an evolution blog rather than a series-of-numbers-in-an-equation-blog, this should be obvious.

Once last comment here. This blog is about the "endless dispute between evolution and creationism." Let me correct that. This is a time-defined dispute (not endless) on a political stage between a very narrow, specific version of christian creationism based in few denominations predominate in certain parts of the US trying to make political hay and a small handful of folks who believe that evolution is the opposite of that. Both sides are sadly mistaken.

Dear Mr. Rosenhouse we are Math students of Universidad Católica del Maule in Chile, we will be Math professor and we liked her blog because has interesting and different topics so scientific as humanities.
We would like more information about Math, suggested books, and other thing in relation with it.
But, regarding to proof Fermat's Little Theorem is very interesting and simple for understand, for us is a extra motivation know the theorem, Math's Mistery, paradoxes about numbers, History of Math.
The Evolution Blog really was a input for us, and we will continue visiting to learn more thing about wonderful world of Math.
Thank you by blog, goodbye
Sergio Lizana and Cristóbal Matamala

By Sergio Lizana Campos (not verified) on 29 Jul 2010 #permalink

ZERTRAT,
while i agree with you on the final sentence in your second post... i just want to say that you also are confused on the issue of mathematics. You see,the mathematics, by enlarge holds validity due to the very truths that this evolutionary process of life has created...