Legendre symbol and quadratic reciprocity. #
This file contains results about quadratic residues modulo a prime number.
We define the Legendre symbol $\Bigl(\frac{a}{p}\Bigr)$ as legendre_sym p a
.
Note the order of arguments! The advantage of this form is that then legendre_sym p
is a multiplicative map.
The Legendre symbol is used to define the Jacobi symbol, jacobi_sym a b
, for integers a
and (odd) natural numbers b
, which extends the Legendre symbol.
Main results #
We prove the law of quadratic reciprocity, see legendre_sym.quadratic_reciprocity
and
legendre_sym.quadratic_reciprocity'
, as well as the
interpretations in terms of existence of square roots depending on the congruence mod 4,
zmod.exists_sq_eq_prime_iff_of_mod_four_eq_one
, and
zmod.exists_sq_eq_prime_iff_of_mod_four_eq_three
.
We also prove the supplementary laws that give conditions for when -1
or 2
(or -2
) is a square modulo a prime p
:
legendre_sym.at_neg_one
and zmod.exists_sq_eq_neg_one_iff
for -1
,
legendre_sym.at_two
and zmod.exists_sq_eq_two_iff
for 2
,
legendre_sym.at_neg_two
and zmod.exists_sq_eq_neg_two_iff
for -2
.
Implementation notes #
The proofs use results for quadratic characters on arbitrary finite fields
from number_theory.legendre_symbol.quadratic_char
, which in turn are based on
properties of quadratic Gauss sums as provided by number_theory.legendre_symbol.gauss_sum
.
Tags #
quadratic residue, quadratic nonresidue, Legendre symbol, quadratic reciprocity
Definition of the Legendre symbol and basic properties #
The Legendre symbol of a : ℤ
and a prime p
, legendre_sym p a
,
is an integer defined as
0
ifa
is0
modulop
;1
ifa
is a nonzero square modulop
-1
otherwise.
Note the order of the arguments! The advantage of the order chosen here is
that legendre_sym p
is a multiplicative function ℤ → ℤ
.
Equations
- legendre_sym p a = ⇑(quadratic_char (zmod p)) ↑a
We have the congruence legendre_sym p a ≡ a ^ (p / 2) mod p
.
If p ∤ a
, then legendre_sym p a
is 1
or -1
.
The Legendre symbol is multiplicative in a
for p
fixed.
The Legendre symbol depends only on a
mod p
.
When p ∤ a
, then legendre_sym p a = 1
iff a
is a square mod p
.
legendre_sym p a = -1
iff a
is a nonsquare mod p
.
Applications to binary quadratic forms #
The Legendre symbol legendre_sym p a = 1
if there is a solution in ℤ/pℤ
of the equation x^2 - a*y^2 = 0
with y ≠ 0
.
The Legendre symbol legendre_sym p a = 1
if there is a solution in ℤ/pℤ
of the equation x^2 - a*y^2 = 0
with x ≠ 0
.
The value of the Legendre symbol at -1
#
See jacobi_sym.at_neg_one
for the corresponding statement for the Jacobi symbol.
legendre_sym p (-1)
is given by χ₄ p
.
The value of the Legendre symbol at 2
and -2
#
See jacobi_sym.at_two
and jacobi_sym.at_neg_two
for the corresponding statements
for the Jacobi symbol.
legendre_sym p 2
is given by χ₈ p
.
legendre_sym p (-2)
is given by χ₈' p
.
The Law of Quadratic Reciprocity #
See jacobi_sym.quadratic_reciprocity
and variants for a version of Quadratic Reciprocity
for the Jacobi symbol.
The Law of Quadratic Reciprocity: if p
and q
are distinct odd primes, then
(q / p) * (p / q) = (-1)^((p-1)(q-1)/4)
.
The Law of Quadratic Reciprocity: if p
and q
are odd primes and p % 4 = 1
,
then (q / p) = (p / q)
.
The Law of Quadratic Reciprocity: if p
and q
are primes that are both congruent
to 3
mod 4
, then (q / p) = -(p / q)
.