If is prime, and , (i.e. ) then
Or equivalently, if is prime, then
Stated by Fermat 1640. Proved by Euler 1736, and by Leibniz (unpublished) about 50 years before that.
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