Let the multiples 
,
, ..., ![[(p-1)/2]m](/images/equations/GausssLemma/Inline3.svg)
of an integer such that
be taken. If there are an even number 
of least positive residues
mod 
of these numbers 
, then 
is a quadratic residue
of 
. If 
is odd, 
is a quadratic nonresidue.
Gauss's lemma can therefore be stated as 
, where 
is the Legendre symbol.
It was proved by Gauss as a step along the way to the quadratic
reciprocity theorem (Nagell 1951).
The following result is known as Euclid's lemma, but is incorrectly termed "Gauss's Lemma" by Séroul (2000, p. 10).
Euclid's lemma states that for any two integers
and 
, suppose 
. Then if 
is relatively prime to
, then 
divides 
.
