Gauss’ lemma

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 thenumber 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

\\left(\\frac{n}{p}\\right)=(-1)^{u}

where $\\left(\\frac{n}{p}\\right)$ 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 $\\mathbbmss{F}_{p}$ for the field of $p$ elements, andidentify $\\mathbbmss{F}_{p}$ with the set $\\{0,1,\\ldots,p-1\\}$ ,with its addition and multiplication mod $p$ .

Proposition 2: Let $S$ be a subset of $\\mathbbmss{F}_{p}^{*}$ such that $x\\in S$ or $-x\\in S$ , but not both, for any $x\\in\\mathbbmss{F}_{p}^{*}$ .For $n\\in\\mathbbmss{F}_{p}^{*}$ let $u(n)$ be the number of elements $k\\in S$ such that $kn\otin S$ . Then

\\left(\\frac{n}{p}\\right)=(-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=\\left(\\frac{n}{p}\\right)\\prod_{a\\in S}a

by Euler’s criterion. So

\\left(\\frac{n}{p}\\right)\\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 thatfor any odd prime $p$ :

\\left(\\frac{-1}{p}\\right)=\\begin{cases}1&\\textrm{ if $p\\equiv 1\\pmod{4}$}\\\\-1&\\textrm{ if $p\\equiv-1\\pmod{4}$}\\end{cases}

\\left(\\frac{2}{p}\\right)=\\begin{cases}1&\\textrm{ if $p\\equiv\\pm 1\\pmod{8}$}\\\\-1&\\textrm{ if $p\\equiv\\pm 3\\pmod{8}$}\\end{cases}

The condition on $S$ can also be stated like this:for any square $x^{2}\\in\\mathbbmss{F}_{p}^{*}$ , there is a unique $y\\in S$ suchthat $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:

\\left(\\frac{n}{p}\\right)=\\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”, withoutleaning on Euler’s criterion, the existence of a primitiveroot, or the fact that a polynomial over $\\mathbbmss{F}_{p}$ has no more zerosthan its degree.