I would also like to add a different proof of Fermats little theorem ($p|(a^p-a)$ for prime $p$) to the list.

Suppose you have a colors of pearls and you want to produce pearl-chains of length $p$.

First you put $p$ pearls on a string. There are $a^p$ possibilities. Next you discard the mono-colored ones, they are boring. This leads to $a^p-a$ choices.

Next you put a knot into the string to turn it to a circular chain.

Now you have each type of chain multiple times, since cyclic permutations give you the same chain.

Finally you have to convince yourself that each type of chain arises in exactly $p$ ways using that $p$ is prime. Thus there are $(a^p-a)/p$ such different chains and hence that number has to be an integer.