Lemmas of Gauss and Eisenstein #
This file contains the Lemmas of Gauss and Eisenstein on the Legendre symbol.
The main results are ZMod.gauss_lemma
and ZMod.eisenstein_lemma
.
The image of the map sending a nonzero natural number x ≤ p / 2
to the absolute value
of the integer in (-p/2, p/2]
that is congruent to a * x mod p
is the set
of nonzero 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 of 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.