my favorite proof of fermat's little theorem

---

One of the first things you learn when you learn in elementary number theory is Fermat's Little Theorem (so named to differentiate it from the big bad Last Theorem).

Theorem. (Fermat's Little Theorem) Let $p$ be a prime number and $a$ be an integer. Then

$$a^{p}\equiv a \pmod p.$$

There are many proofs of this theorem, but my favorite one is a combinatorial proof that goes by counting necklaces. Suppose you have $a$ different colored beads. Then the number of length-$p$ strings you can make is $a^p$, since you have $a$ choices for each of the $p$ beads.

(We'll take $a = 2$ and $p = 3$ for the images, but the argument holds generally.)

Notice that exactly $a$ of these have beads all of the same color, one for each color:

Put those aside and consider the rest of the strings. Batch¹ together the strings that form the same necklace (up to rotation) when you join the ends — that is, batch together the strings that differ only by a shift.

Because $p$ is prime, shifting any string by $1, \dots, p-1$ spaces gives a different string every time. So each batch has $p$ strings in it.² Then

$$a^{p}= \underbrace{\text{\# of different-colored strings}}_{\text {multiple of } p} + \underbrace{\text{\# of same-colored strings}}_{a},$$

which is exactly saying that

$$a^{p}\equiv a \pmod p. \qquad{(*)}$$

This is what we wanted! Except that the astute among you have noticed that in original theorem statement, $a$ is allowed to be negative.³ But fear not! If $p$ is odd, you can just multiply the congruence in $(*)$ by $-1$. If $p = 2$, well, it amounts to proving that squaring preserves parity. (Exercise!)

Now we're done. $\blacksquare$

Like I said, there are other ways to prove this theorem, some of which don't require this goofy "well, actually" at the end. But I like this one in particular because it has such a nice group action flavor.

We can think of the shifting as the group $\mathbb{Z}/ p\mathbb{Z}$ acts on the set of strings of length $p$ — an element $z \in \mathbb{Z}/ p\mathbb{Z}$ acts on a string by shifting it by $z$. From a group action perspective, the strings of all one color we were looking at earlier are special. They are the fixed points of the group action, because they are unchanged by any group element acting on them.

The key idea of the necklace proof was comparing the total size of the set of strings with the number of fixed points, modulo $p$. It turns out that what we saw was a special case of a broader fact about group actions, called the fixed point congruence.

Lemma. (Fixed point congruence). Let $P$ be a group of order $p^i$ for some prime $p$, and let $P$ act on a set $X$. Then

$$|X| \equiv |\text{fix}_P(X)| \pmod p$$

where $\text{fix}_P(X) = \set{x\in X \mid gx = x \text{ for all } g \in P}$.

I won't go into the proof here, but the idea is very similar to the "batch things together" approach we used above, just applied more abstractly using the orbit-stabilizer theorem.

This is a pretty powerful lemma, used in the proof of all three Sylow theorems. But for our purposes, we'll just note that $\mathbb{Z}/ p\mathbb{Z}$ is a group of prime power order and then use the lemma to reframe the necklace proof using group actions.

Proof of Fermat's Little Theorem. (By group action). First we note that it is enough to prove the nonnegative case, since $a^p \equiv a \pmod p$ if and only if $(-a)^{p}\equiv -a^{p} \equiv-a \pmod p$.⁴

Let $S$ be the set of strings of $p$ beads, where each bead can be one of $a$ colors.⁵ Observe that $|S|=a^p$. Let $\mathbb{Z}/p\mathbb{Z}$ act on $S$ by translation. Observe that the only fixed points of this action are the strings where the beads are all the same color, so there are $a$ fixed points (one for each color). Hence, by the fixed-point congruence, $a^p \equiv a \pmod p$. $\blacksquare$

It's a little overkill, but I still like it.

footnotes

---

1. I really want to say "group together," but the word "group" means something else in math land and English has a dearth of words that I could use in its stead. Please bear with the awkward wording ;-; ↩

2. Make sure you believe it! ↩

3. Wait a minute, isn't $a$ allowed to be zero, too? Yes, but it's totally legal to follow the proof by having $0$ different colors of beads. Or you can observe that the conclusion is trivial if $a = 0$. Whatever floats your boat. ↩

4. This is our "well, actually" from above. ↩

5. Or the set of words of length $p$ from an alphabet of $a$ letters, if you like. ↩