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 .