Legendre symbol and quadratic reciprocity. #
This file contains results about quadratic residues modulo a prime number.
We define the Legendre symbol
(a / p) as
legendre_sym p a.
Note the order of arguments! The advantage of this form is that then
is a multiplicative map.
The main results are the law of quadratic reciprocity,
quadratic_reciprocity, as well as the
interpretations in terms of existence of square roots depending on the congruence mod 4,
Also proven are conditions for
2 to be a square modulo a prime,
Implementation notes #
The proof of quadratic reciprocity implemented uses Gauss' lemma and Eisenstein's lemma
The Legendre symbol of
a : ℤ and a prime
legendre_sym p a,
is an integer defined as
ais a square modulo
Note the order of the arguments! The advantage of the order chosen here is
legendre_sym p is a multiplicative function
ℤ → ℤ.
Gauss' lemma. The legendre symbol can be computed by considering the number of naturals less
p/2 such that
(a * x) % p > p / 2