# 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).

Full article ▸

 related documents Simplex Frame problem Factorial Absolute value Interval (mathematics) Hash function Compass and straightedge constructions Group action Prime number theorem Abelian group Dynamic programming Multivariate normal distribution Computable number Fundamental group Hyperreal number Central limit theorem Huffman coding Convolution Continuous function RSA Primitive recursive function Euler's formula Dual space Lua (programming language) Bessel function Fundamental theorem of algebra Basis (linear algebra) Gaussian elimination BCH code Ackermann function