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