Fermat's little theorem
ProvedFamousTheorems.pow_card_sub_one_eq_oneFermat's little theorem.
For a prime and ,
Equivalently for every . The statement is that the multiplicative group of has order , so Lagrange's theorem kills every element on raising to that power — which is why the hypothesis is exactly , the condition for to lie in that group at all.
Fermat announced it in a 1640 letter to Frénicle, characteristically without proof; Euler published the first one in 1736 and later generalised it to for arbitrary modulus. It is the basis of Fermat primality testing and, through its Euler generalisation, of RSA: the decryption exponent works precisely because .
The converse fails — the Carmichael numbers, of which is the smallest, satisfy the congruence for every coprime base without being prime — which is why probabilistic primality tests need the stronger Miller–Rabin refinement.
Formalization note. ZMod p is the integers mod and Fact p.Prime supplies the field
structure, so a ≠ 0 is literally the unit condition. The result is Mathlib's
ZMod.pow_card_sub_one_eq_one.
import Mathlib
namespace FamousTheorems
open MeasureTheory ProbabilityTheory Filter Set
open scoped Topology ENNReal NNReal
theorem pow_card_sub_one_eq_one {p : ℕ} [Fact p.Prime] {a : ZMod p} (ha : a ≠ 0) :
a ^ (p - 1) = 1 := by sorry
end FamousTheorems