fermat_little_theorem
Provedmodular-arithmeticnumber-theoryproved
Fermat's little theorem: For prime p and gcd(a,p)=1, a^{p-1} ≡ 1 (mod p). Proved by Fermat (1640), Euler (1736). Basis of many primality tests and RSA encryption.
Preamble
import Mathlib
Formal statement
import Mathlib
theorem fermat_little_theorem (p : ℕ) (hp : Nat.Prime p) (a : ℤ) (ha : ¬ (p : ℤ) ∣ a) :
a ^ (p - 1) ≡ 1 [ZMOD p] := by
sorrySource