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