Fermat's Little Theorem

Let be an arbitrary prime number, and be an arbitrary integer not divisible by .
Since , we have (see congruence class)

We prove the equivalent result, that for all prime numbers and non-zero elements in , we have

Now consider the list of elements

in . Next, we prove two facts about this list:

1. The element does not exist in the list
2. The elements in the list are all distinct

For fact 1, assume for the sake of contradiction, that does appear in the list, and hence that for some .
By the corollary Inverses in Z_m, has a multiplicative inverse, and multiplying on both sides of the above equation by , we obtain .
Using modular arithmetic, LS = , RS = , so we get , which is a contradiction.

For fact 2, assume for the sake contradiction, that two elements in the list are the same, and hence that for some and with and .
Multiplying on both sides of the above equation by , we obtain .
Using modular arithmetic, LS = , and RS = , so we get , which is a contradiction.

Putting facts 1 and 2 together, means the elements in the list

must be non-zero elements in in some order.
Since lists (1) and (2) consist of the same elements in possible different order, the products of the two lists must be equal. Hence

and factoring each , for on the left hand side, gives

Now from the corollary Inverses in Z_p, exists for all , and multiplying on both sides of the above equation by , we obtain

Let be an arbitrary prime number and be an arbitrary integer. Note that is either divisible by or not divisible by (see tautology)

In the case that is divisible by , we have . Hence , so we have in this case.

In the case that , then by FℓT, we have . Multiplying on both sides by gives in this case as well.