Gauss' lemma on quadratic residues is:

Proposition 1: Let $p$ be an odd prime and let $n$ be an integer which is not a multiple of $p$ . Let $u$ be the number of elements of the set $$\left\{n,2n,3n,\ldots,\frac{p-1}{2}n\right\}$$ whose least positive residues, modulo $p$ , are greater than $p/2$ . Then $$\legsymp{n}=(-1)^u$$ where $\legsymp{n}$ is the Legendre symbol.

That is, $n$ is a quadratic residue modulo $p$ when $u$ is even and it is a quadratic nonresidue when $u$ is odd.

Gauss' Lemma is the special case $$ S=\left\{1,2,\ldots,\frac{p-1}{2}\right\ $$ of the slightly more general statement below. Write for the field of $p$ elements, and identify with the set $\{0,1,\ldots,p-1\}$ , with its addition and multiplication mod $p$ .

Proposition 2: Let $S$ be a subset of such that $x\in S$ or $-x\in S$ , but not both, for any . For let $u(n)$ be the number of elements $k\in S$ such that $kn\notin S$ . Then $$\legsymp{n} = (-1)^{u(n)}.$$ Proof: If $a$ and $b$ are distinct elements of $S$ , we cannot have $an=\pm bn$ , in view of the hypothesis on $S$ . Therefore $$\prod_{a\in S}an=(-1)^{u(n)}\prod_{a\in S}a.$$ On the left we have $$n^{(p-1)/2}\prod_{a\in S}a=\legsymp{n}\prod_{a\in S}a$$ by Euler's criterion. So $$\legsymp{n}\prod_{a\in S}a=(-1)^{u(n)}\prod_{a\in S}a$$ The product is nonzero, hence can be cancelled, yielding the proposition.

Remarks: Using Gauss' Lemma, it is straightforward to prove that for any odd prime $p$ :

The condition on $S$ can also be stated like this: for any square , there is a unique $y\in S$ such that $x^2=y^2$ . Apart from the usual choice $$S=\{1,2,\ldots,(p-1)/2\}\;,$$ the set $$\{2,4,\ldots,p-1\}$$ has also been used, notably by Eisenstein. I think it was also Eisenstein who gave us this trigonometric identity, which is closely related to Gauss' Lemma: $$\legsymp{n}=\prod_{a\in S}\frac{\sin{(2\pi an/p)}}{\sin{(2\pi a/p)}}$$

It is possible to prove Gauss' Lemma or Proposition 2 ``from scratch'', without leaning on Euler's criterion, the existence of a primitive root, or the fact that a polynomial over has no more zeros than its degree.