I am trying to digest the necklace-counting combinatorial proof for Fermat's little theorem given in Wikipedia as per June-13th, 2021. The steps I am having trouble with the conclusion:
The second category contains $a^p−a$ strings, and they may be arranged into groups of $p$ strings, one group for each necklace. Therefore, $a^p−a$ must be divisible by $p$, as promised
How exactly did Wikipedia conclude that last statement generally?
They have shown example for $2^5$ but I just can't understand how one could conclude it generally from the example shown.
There are $a$ symbols, leading to $a^p$ necklaces, $a$ of which have just one symbol in them (repeated $p$ times). Consider the remaining $a^p-a$ necklaces. We say that two necklaces are equivalent if they can be turned into each other by rotation.
Now these $a^p-a$ necklaces can be partioned into a number of equivalence classes. If we can show that each equivalence class contains precisely $p$ elements, then $p\mid a^p-a$ and we are done.
This is equivalent to the following: if we take a necklace which has more than one distinct symbol in it, and rotate it so that it doesn't change, then we didn't rotate it at all (or, if you're familiar with these terms: The stabilizer of the necklace under the action of the cyclic group of order $p$ consists of just the identity)
Now let's prove this: Suppose our the values in the necklace are $v_0,v_2,\ldots,v_{p-1}$ and a rotation by $1\le l\le p-1$ doesn't change the necklace. Then $v_0=v_l=v_{2l}=\cdots$ and $v_1=v_{l+1}=\cdots$ and so on. In other words, the values are just $v_0,\ldots v_{l-1}$ repeated over and over. But our necklace has length $p$, so $l\mid p$. This means that $l=1$ and the necklace contains only one distinct value; a contradiction.