Fermat’s Little Theorem: proof by necklaces

It’s time for our second proof of Fermat’s Little Theorem, this time using a proof by necklaces. As you know, proof by necklaces is a very standard technique for… wait, what do you mean, you’ve never heard of proof by necklaces?! Honestly, what do they teach in schools these days…?

…just kidding! I’ll explain what necklaces are in a minute. But first, let me state that we will be proving statement (3) of FlT, namely,

If $p$ is prime and $a$ is any integer, then $a^p \equiv a \pmod p$ .

Subtracting $a$ from both sides, this is the same as saying that $a^p - a \equiv 0 \pmod p$ , which is in turn the same as saying that $a^p - a$ is evenly divisible by $p$ . As we have already seen, this statement is equivalent to the other statements (1) and (2) of Fermat’s Little Theorem.

Now, this is a necklace:

That is, a necklace is a circular arrangement of colored beads. (I’ve also labelled each bead with a number corresponding to its color, to make it easier to distinguish them.) Two necklaces are the same if they are rotations of each other. For example, these three necklaces, although they are drawn differently, are all the same:

Unlike in real life, though, we’re not allowed to flip necklaces over,¹ so these two necklaces are different:

Now, suppose we have $a$ different bead colors to choose from. Assume that we have a plentiful supply of each bead color, so we can use as many beads of each color as we want. Here is the central question we will consider:

How many necklaces are there with exactly $p$ beads and at least two different colors?

We will show that there are in fact $\displaystyle\frac{a^p - a}{p}$ such necklaces—and since the number of necklaces is obviously an integer, this means that $p$ must evenly divide $a^p - a$ . So, on with the proof!

If you cut a necklace in between two beads and open it up, you get a strand (also commonly called a string or a word). Like this:

Let’s start by counting strands. First, the number of different strands with $p$ beads chosen from $a$ possible colors is $a^p$ : for each one of the $p$ beads we can independently choose any one of the $a$ available colors, for a total of $\underbrace{a \cdot a \cdot \dots \cdot a}_p = a^p$ choices. For example, if $a = 2$ and $p = 5$ , here are the $2^5 = 32$ different possible strands with $5$ beads and (up to) two colors:

Notice that we don’t have to use all the colors in each strand. $a$ is the number of available colors, but just because a color is available doesn’t mean we have to use it. As another example, here are the $3^3 = 27$ strands with three beads chosen from among three available colors:

Now, some of these strands use only a single color, that is, all their beads are the same color. In fact, there are exactly $a$ such strands, one for each color. So the number of strands with at least two different colors is $a^p - a$ : the total number of strands minus the strands with only one color.

So, how many necklaces are there? Let’s work backwards: think about starting with a necklace and cutting it at various points to create different strands. For example, if we start with the necklace shown below and cut it in all five possible locations, we get five distinct strands:

You can check that these five strands are all different. However, this is not always the case. For example, cutting the necklace shown below yields only three different strands:

I’ve drawn six strands above, representing all six possible cuts, but as you can see, they are not all unique—in fact, there are two copies of each strand.

What’s the difference? Well, the difference is that $5$ is prime whereas $6$ is not! Remember that we assumed $p$ , the length of our necklaces, is prime. And I claim that every necklace of prime size $p$ , that uses two or more colors, yields exactly $p$ distinct strands when cut.

Why is that? Think about what it means if a necklace yields the same strand when cut in two different places which are spaced $k$ beads apart. (In the example shown above, $k = 3$ .) Since the strands are the same, the beads right after each cut must be the same; the beads two places after each cut must be the same, the beads three places after each cut must be the same, and so on—in general, if you look at any two beads spaced $k$ apart, they must be the same. But this means that the whole necklace has a period of $k$ —that is, the necklace consists of a group of $k$ beads which is repeated some number of times. But if the whole necklace is made up of some number of repetitions of a group of $k$ beads, that means $k$ must evenly divide the size of the necklace $p$ . But if $p$ is prime, the only way for this to happen is if $k = 1$ , in which case the necklace consists of a single repeated bead, that is, the necklace only has one color.

So, when $p$ is prime, each necklace with at least two bead colors corresponds to exactly $p$ different strands—and each strand corresponds to exactly one necklace (the one you get when you glue the ends of the strand together). For example, here is the correspondence between the $6$ different necklaces of size $p = 5$ with at least two colors chosen out of $a = 2$ , and the $a^p - a = 2^5 - 2 = 30$ different strands containing both colors. Each necklace corresponds to exactly $5$ different strands.

We already know there are $a^p - a$ strands with at least two colors; since we can put them in groups of $p$ , one for each necklace of at least two colors, $a^p - a$ must be evenly divisible by $p$ . QED!

Circular arrangements of beads which are considered the same up to rotations and flips are usually called bracelets.↩

4 Responses to Fermat’s Little Theorem: proof by necklaces

Anthony says:

December 12, 2017 at 6:24 pm

Nice proof. Haven’t seen it before.
Naren Sundar says:

December 18, 2017 at 8:15 pm

Neat!
Pingback: The Necklace proof – The nth Root
Pingback: Orthogon equivalence and orthogonal vertex sequences | The Math Less Traveled

Comments are closed.