Gauss's theorem on primitive roots
ProvedFamousTheorems.gauss_primitive_root_theoremGauss's theorem on primitive roots. For a positive integer , the group is cyclic (that is, there is a primitive root modulo ) if and only if
for an odd prime and .
Gauss proved this in the Disquisitiones Arithmeticae (1801). Primitive roots give discrete logarithms modulo , the index calculus, and the structure of -th power residues. They also underlie the Diffie–Hellman and ElGamal cryptosystems.
Formalization note. Mathlib's ZMod.isCyclic_units_iff. It also includes , where ZMod 0 = ℤ has unit group , which is cyclic.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem gauss_primitive_root_theorem (n : ℕ) :
IsCyclic (ZMod n)ˣ ↔
n = 0 ∨ n = 1 ∨ n = 2 ∨ n = 4 ∨ ∃ p m : ℕ, p.Prime ∧ Odd p ∧ 1 ≤ m ∧ (n = p ^ m ∨ n = 2 * p ^ m) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `ZMod.isCyclic_units_iff`. Proof here reduces to that Mathlib result.