Gauss's lemma on quadratic residues
ProvedFamousTheorems.gauss_lemma_quadratic_residuesGauss's lemma on quadratic residues. Let be an odd prime and an integer not divisible by . Let be the number of for which the least nonnegative residue of modulo exceeds . Then the Legendre symbol is
Gauss used this lemma in one of his proofs of quadratic reciprocity. It also gives the supplementary law directly. Eisenstein's lattice-point proof of reciprocity is based on it.
Formalization note. Mathlib's ZMod.gauss_lemma. legendreSym p a is the Legendre symbol. ZMod.val is the least nonnegative residue in . The range is Finset.Ico 1 (p / 2).succ, and "exceeds " is p / 2 < val with natural-number division.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem gauss_lemma_quadratic_residues {p : ℕ} [Fact p.Prime] {a : ℤ} (hp : p ≠ 2) (ha0 : (a : ZMod p) ≠ 0) :
legendreSym p a =
(-1) ^ ((Finset.Ico 1 (p / 2).succ).filter
(fun x : ℕ => p / 2 < ((a : ZMod p) * (x : ZMod p)).val)).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `ZMod.gauss_lemma`. Proof here reduces to that Mathlib result.