cronaldo··on Annotated Combinatorial Proof of Fermat’s “Little” TheoremThere's also a very interesting proof without using any analogue of the Euclidean algorithm - http://arxiv.org/pdf/0801.0805v3.pdf