# Proofs of Fermat's little theorem

 related topics {math, number, function} {math, energy, light} {film, series, show} {work, book, publish}

This article collects together a variety of proofs of Fermat's little theorem, which states that

for every prime number p and every integer a (see modular arithmetic).

## Contents

### Simplifications

Some of the proofs of Fermat's little theorem given below depend on two simplifications.

The first is that we may assume that a is in the range 0 ≤ ap − 1. This is a simple consequence of the laws of modular arithmetic; we are simply saying that we may first reduce a modulo p.

Secondly, it suffices to prove that

for a in the range 1 ≤ ap − 1. Indeed, if (X) holds for such a, then we can simply multiply both sides by a to obtain the original form of the theorem,

and if a happens to be zero, the original equation in its original form is obviously true anyway.

### Proof by counting necklaces

This is perhaps the simplest known proof, requiring the least mathematical background. It is an attractive example of a combinatorial proof (a proof that involves counting a collection of objects in two different ways).