Fermat's little theorem

Statement

Fermat's little theorem

For any prime number and we have

Proof

Note if is a multiple of the statement is true as both sides are zero. It suffices to prove this for as all other integers are congruent to one of these mod . Moreover, we only need to show (mod ).

Consider the set . From the proof of Modular multiplicative inverse existence we know .

Therefore by multiplying the entries in together we have However as for is coprime to from modular multiplicative inverse existence lemma. We know therefore has a multiplicative inverse mod . So we have as desired.

Theory

This is generalised by Euler’s theorem (modular arithmetic).