Euler's criterion
ProvedFamousTheorems.euler_criterion_zmodEuler's criterion. Let be a prime and a nonzero element of . Then is a square modulo if and only if
For odd this gives the formula for the Legendre symbol. It is the basis of fast quadratic-residuosity tests and of the Solovay–Strassen primality test. It also gives the first supplementary law: is a square modulo an odd prime exactly when .
Formalization note. Mathlib's ZMod.euler_criterion. IsSquare a means for some r : ZMod p. The exponent is p / 2 with natural-number division, which equals for odd . For both sides hold for .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem euler_criterion_zmod (p : ℕ) [Fact p.Prime] {a : ZMod p} (ha : a ≠ 0) : IsSquare a ↔ a ^ (p / 2) = 1 := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `ZMod.euler_criterion`. Proof here reduces to that Mathlib result.