Lemmas of Gauss and Eisenstein #
This file contains code for the proof of the Lemmas of Gauss and Eisenstein
on the Legendre symbol. The main results are zmod.gauss_lemma_aux
and
zmod.eisenstein_lemma_aux
.
The image of the map sending a non zero natural number x ≤ p / 2
to the absolute value
of the element of interger in the interval (-p/2, p/2]
congruent to a * x
mod p is the set
of non zero natural numbers x
such that x ≤ p / 2
Gauss' lemma. The legendre symbol can be computed by considering the number of naturals less
than p/2
such that (a * x) % p > p / 2
Each of the sums in this lemma is the cardinality of the set integer points in each of the
two triangles formed by the diagonal of the rectangle (0, p/2) × (0, q/2)
. Adding them
gives the number of points in the rectangle.