Annotated Combinatorial Proof of Fermat’s “Little” Theorem

There's also a very interesting proof without using any analogue of the Euclidean algorithm - http://arxiv.org/pdf/0801.0805v3.pdf