TOPICS

# Gauss's Lemma

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

More things to try:

## 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