Given the size of an alphabet = r and given the length of string made with this alphabet = p, I am asked to prove (r^p - r)mod p = 0.
Looking up the solution it is said that there is r strings of the same character p times each belonging to an equivalence class. I can't grasp what this sentence mean. It is then said that there is (r^p - r) other strings belonging to equivalence classes. Here I am completely lost by what the sentence mean.
On top of that I of course do not understand how this is a proof for the little fermat theorem.
You can define an equivalence relation $\sim$ on the set of strings with $p$ characters of letters of your alphabet as follows:$$a_1a_2\ldots a_p\sim b_1b_2\ldots b_p$$if the string $b_1b_2\ldots b_p$ is equal to one of the strings$$a_1a_2\ldots a_p,a_2a_3\ldots a_pa_1,a_3a_4\ldots a_1a_2,\ldots,a_pa_1a_2\ldots a_{p-1}.\tag1$$There are $r^p$ strings at all. Each string with $p$ equal characters is equivalent to itself and only to itself. Besides this case, the equivalence class of $a_1a_2\ldots a_p$ consists of the $p$ elements from $(1)$ — it is here that the fact that $p$ is prime is used. But then the $r^p-r$ non-constant sstrings can be divided into groups of $p$ elements and therefore $p\mid r^p-r$.