# Fermat’s little theorem

If is prime, and , (i.e. ) then

(1)

Or equivalently, if is prime, then

(2)

Stated by Fermat 1640. Proved by Euler 1736, and by Leibniz (unpublished) about 50 years before that.

Proof
means that has an inverse , i.e. there’s a number such that .
The numbers also have inverses , because is prime.
Consider the remainders of on division by :

These are the numbers again in a different order, as they are nonzero and unequal , since would imply . It follows that:

Proof by induction (for )
1. When , obviously .
2. Assuming is true for every prime , prove .
From the binomial theorem,

Since divides each of the integers

We have assumed that , so

QED