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
-
M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted
in 1997.