Quadratic reciprocity for the Jacobi symbol
ProvedFamousTheorems.jacobi_quadratic_reciprocityQuadratic reciprocity for the Jacobi symbol. For odd natural numbers and ,
where is the Jacobi symbol.
This extends Gauss's quadratic reciprocity law from odd primes to all odd moduli. Unlike the Legendre symbol, the Jacobi symbol can be computed by a Euclid-like algorithm without factoring, because of this law. This is what makes the Solovay–Strassen primality test and fast Legendre-symbol evaluation possible.
Formalization note. Mathlib's jacobiSym.quadratic_reciprocity. The exponent is written as a / 2 * (b / 2) with natural-number division, which equals for odd . The symbol is jacobiSym (a : ℤ) b, and no coprimality assumption is needed (both sides vanish otherwise).
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem jacobi_quadratic_reciprocity {a b : ℕ} (ha : Odd a) (hb : Odd b) :
jacobiSym (a : ℤ) b = (-1) ^ (a / 2 * (b / 2)) * jacobiSym (b : ℤ) a := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `jacobiSym.quadratic_reciprocity`. Proof here reduces to that Mathlib result.