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:


\[
\textrm{Let } k \textrm{ be a positive integer and let } p \textrm{ be a prime number }.
\]

 


\[
\textrm{Then } k^p - k \textrm{ 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^3 - 2 = 8 - 2 = 6
\]

 

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


\[
4^3 - 4 = 64 - 4 = 60 \phantom{xxx} \textrm{and} \phantom{xxx}
5^3 - 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 \phantom{xxx} \textrm{and} \phantom{xxx} k = 7.
\]

 

This time we get


\[
7^{11} - 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 \phantom{x} \textrm{is a multiple of} \phantom{x} p.
\]

 

That is equivalent to showing that the fraction


\[
\frac{k^p - k}{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 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 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


\[
\frac{k^p - k}{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, Red, Green, Blue, Red

 

If we shift everything once we get


Blue, Red, Green, Blue, Red, Green

 

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


Red, Green, Blue, Red, Green, Blue

 

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


Green, Blue, Red, Green, Blue, Red

 

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.

Comments

  1. #1 rpenner
    March 1, 2011

    7^11 should be 7^{11}

  2. #2 Jason Rosenhouse
    March 1, 2011

    Fixed! Thanks for pointing out the error.

  3. #3 D. C. Sessions
    March 1, 2011

    I’m not sure what rendering plugin you’re using, but maybe you could use SVG or something to keep us from having to decode TeX ourselves?

  4. #4 eric
    March 1, 2011

    Should it read “let k be a positive integer greater than 1″? Plugging the integer 1 in for k does not lead to multiple of k.

  5. #5 James Sweet
    March 1, 2011

    Plugging the integer 1 in for k does not lead to multiple of k

    I assume you mean “multiple of p”, but either way, sure it does!

    Let k = 1. We then have:

    $$1^{p} – 1 = 1 – 1 = 0$$

    And last time I checked, 0 was a multiple of everything :)

  6. #6 Jon Wharf
    March 1, 2011

    And on to Carmichael numbers?

  7. #7 Lenoxuss
    March 2, 2011

    I love these sort of “casual proofs” that appeal to intuition. Makes me think of a few of the examples in A Mathematician’s Lament. Yay math!

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.