Gauss's Lemma

Let the multiples $m$, $2m$, ..., $[(p-1)/2]m$ of an Integer such that $p\notdiv m$ be taken. If there are an Even number $r$ of least Positive Residues mod $p$ of these numbers $>p/2$, then $m$ is a Quadratic Residue of $p$. If $r$ is Odd, $m$ is a Quadratic Nonresidue. Gauss's lemma can therefore be stated as $(m\vert p) =(-1)^r$, where $(m\vert p)$ 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