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 .

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.