# 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

$$\{n,2n,3n,\mathrm{\dots},\frac{p-1}{2}n\}$$ |

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=\{1,2,\mathrm{\dots},\frac{p-1}{2}\}$$ |

of the slightly more general statement below. Write ${\mathbb{F}}_{p}$ for the field of $p$ elements, and identify ${\mathbb{F}}_{p}$ with the set $\{0,1,\mathrm{\dots},p-1\}$, with its addition and multiplication mod $p$.

Proposition 2: Let $S$ be a subset of ${\mathbb{F}}_{p}^{*}$ such that $x\in S$ or $-x\in S$, but not both, for any $x\in {\mathbb{F}}_{p}^{*}$. For $n\in {\mathbb{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{array}{cc}1\hfill & \text{if}p\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod4)\hfill \\ -1\hfill & \text{if}p\equiv -1\phantom{\rule{veryverythickmathspace}{0ex}}(mod4)\hfill \end{array}$$ |

$$\left(\frac{2}{p}\right)=\{\begin{array}{cc}1\hfill & \text{if}p\equiv \pm 1\phantom{\rule{veryverythickmathspace}{0ex}}(mod8)\hfill \\ -1\hfill & \text{if}p\equiv \pm 3\phantom{\rule{veryverythickmathspace}{0ex}}(mod8)\hfill \end{array}$$ |

The condition on $S$ can also be stated like this: for any square ${x}^{2}\in {\mathbb{F}}_{p}^{*}$, there is a unique $y\in S$ such that ${x}^{2}={y}^{2}$. Apart from the usual choice

$$S=\{1,2,\mathrm{\dots},(p-1)/2\},$$ |

the set

$$\{2,4,\mathrm{\dots},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{\mathrm{sin}(2\pi an/p)}{\mathrm{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 ${\mathbb{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 |