§ Combinatorial intuition for Fermat's little theorem

We wish to show that $x^p \equiv x (\mod p)$ combinatorially . Let's take $2^3 (\mod 3)$ for simplicity. The general case follows. Let's first write down strings which enumerate $2^3$:

000
001
010
011
100
101
110
111

To make use of $\mod 3$, we're going to treat our strings as necklaces . So, for example, the string 011 looks like:

*-→ 0 -*
|      |
|      ↓
1 ←--- 1

So we have three possible rotations of the string 011:

011
110
101

• Each of these rotations are unique, since they can be totally ordered using lexicographic ordering. Indeed, for any string other than 000, 111, all of its rotations are unique.

• So we can count the above 7 strings with equivalence class representatives. These representatives are those strings that are the lex smallest in their cyclic shifts. (Why are cyclic shifts so important ?)

Cyclic subshifts of strings:
---------------------------
000, 000, 000
001, 010, 100
011, 110, 101
111, 111, 111

• We've written the strings along with their cyclic subshifts, with the representative of the equivalence class as the first element. So the representatitives are 000, 001, 011, 111. Note that two of these ( 000, 111) are equal to their cyclic subshifts. All of the others are distinct, and generate 3 elements.

• So we can count the above strings as:

all strings   = {shifts of 001, 011}U{000, 111}
|all strings| = |{shifts of 001, 011}|+|{000, 111}|
no. of shifts = 3*(no. of representatives)
2^3 = 3 * (no. of representatives) + 2
2^3 = 3 * (no. of representatives) + 2
2^3 % 3 = 2

In general, for x^p % p, we will get x strings that contain the same letter. These will not have elements in their cyclic shift equivalence classes. The other strings will be generated as the smallest cyclic subshift of some string.

§ Why does this not work when p is not prime?

Let p = 4. In this case, I can pick the string s = 0101. It has shifts:

0101 <-
1010
0101 <-
1010

so two of its shifts overlap, hence we will double-count the string 0101 if I counted its equivalence class as having size 4.

§ Relationship to group theory?

• How does this relate to group theory? Well, what we are doing is providing an action of the group Z/pZ into the set of strings X^p where X is some set. Our group action for a number n ∈ Z/pZ takes a string s ∈ X^p to its cyclic shift by n characters.

• We are then using the fact that the orbits of an action when p is prime has size either 1 or p, since the size of the orbit divides the size of the group Z/pZ, which is p, a prime. The divisors of p are only 1 and p. Therefore, the size of the orbit is either 1or p.

• Only necklaces that have identical elements like 000 and 111 have orbits of size 1. We have |X| such necklaces.

• All other necklaces have size p.

• The rest of the proof follows similarly as before.

§ References

• A string of pearls: proofs of Fermat's little theorem
• Algorithms thread 1: division under mod