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 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
Canonical name	GaussLemma
Date of creation	2013-03-22 12:19:46
Last modified on	2013-03-22 12:19:46
Owner	drini (3)
Last modified by	drini (3)
Numerical id	14
Author	drini (3)
Entry type	Theorem
Classification	msc 11A15
Related topic	EulersCriterion
Related topic	ZolotarevsLemma