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$:

000001010011100101110111

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:

011110101

• 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, 000001, 010, 100011, 110, 101111, 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) + 22^3 = 3 * (no. of representatives) + 22^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 <-10100101 <-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