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 Gauß as a step along the way to the Quadratic Reciprocity Theorem.
See also Quadratic Reciprocity Theorem