TheoremProved

Fermat's little theorem

Statement

If $p$ is prime and $a$ is an integer not divisible by $p$ , then $a^{p-1}\equiv 1 \pmod{p}$ .

Why is it true?

Multiplying the numbers $1,2,\dots,p-1$ by $a$ and reducing modulo $p$ just permutes them, since $a$ is invertible mod $p$ . So the product of the permuted list equals the product of the original list; cancelling the common factor $(p-1)!$ leaves $a^{p-1}\equiv 1$ .

Proof sketch

The map $k\mapsto ak\bmod p$ permutes $\{1,\dots,p-1\}$ because $a$ is invertible mod $p$ (as $p\nmid a$ ). Multiplying all residues gives $\prod_{k=1}^{p-1}(ak) \equiv \prod_{k=1}^{p-1} k \pmod p$ , i.e. $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$ . Since $\gcd((p-1)!,p)=1$ , cancel to get $a^{p-1}\equiv 1\pmod p$ .

Stated by

stated 1640Pierre de Fermat

Proved by

proved 1736Leonhard Euler

Topics that use this theorem

Fermat's little theorem and Euler's theorem Congruences and modular arithmetic

Related theorems

Euler's theorem (totient)Wilson's theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Leonhard Euler (1736). Theorematum quorundam ad numeros primos spectantium demonstratio
G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers · DOI:10.1093/oso/9780199219858.001.0001