Fermat’s little theorem: Let p be a prime. Then a^p-a is a multiple of p. In other words a^p is congruent to a mod p.
Proof: We will use Induction. For a=1 we have a^p-a=1^p-1=1-1=0. 0 is a multiple of p.
Now we assume, that the theorem works for a.
Last but not least, we have to show that a+1 works. We have (a+1)^p-(a+1)=(a+1)^p-a-1. Now we use the binomial theorem:
We know that a^p-a is a multiple of p. Every summand of the sum is a multiple of p as well. It follows, that the theorem works for a+1 as well.
This proves the theorem.