Let the multiples ,
, ..., 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 .

See also Euclid's Lemma ,

Legendre
Symbol ,

Quadratic Reciprocity Theorem
Explore with Wolfram|Alpha
References Nagell, T. "Gauss's Lemma." §40 in Introduction
to Number Theory. New York: Wiley, pp. 139-141, 1951. Séroul,
R. "Gauss's Lemma." §2.4.2 in Programming
for Mathematicians. Berlin: Springer-Verlag, pp. 10-11, 2000.
Cite this as:
Weisstein, Eric W. "Gauss's Lemma." From
MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/GausssLemma.html

Subject classifications