Problem 1: Stringologic Proof of Fermat's Little Theorem

In 1640 the great French number theorist Pierre de Fermat proved the following property:

If $p$ is a prime number and $k$ is any natural number then $p$ divides $k^p-k$.

The statement is known as Fermat's little theorem.

Prove Fermat's little theorem using only stringologic arguments.

Count conjugacy classes of words of length $p$.

References