# Gauss’ lemma

Gauss’ lemma on quadratic residues is:

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

 $\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, and identify $\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\notin 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 that for 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$ 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:

 $\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”, without leaning on Euler’s criterion, the existence of a primitive root, or the fact that a polynomial over $\mathbbmss{F}_{p}$ has no more zeros than its degree.

Title Gauss’ lemma GaussLemma 2013-03-22 12:19:46 2013-03-22 12:19:46 drini (3) drini (3) 14 drini (3) Theorem msc 11A15 EulersCriterion ZolotarevsLemma