PlanetMath: Gauss' lemma

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (205)
Orphanage
Unclass'd
Unproven (490)
Corrections (8)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Gauss' lemma

(Theorem)

Gauss' lemma on quadratic residues is:

Proposition 1: Let be an odd prime and let be an integer which is not a multiple of . Let be the number of elements of the set

$\displaystyle \left\{n,2n,3n,\ldots,\frac{p-1}{2}n\right\}$

whose least positive residues, modulo

, are greater than

. Then

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

where $\left(\frac{n}{p}\right)$ is the Legendre symbol.

That is, is a quadratic residue modulo when is even and it is a quadratic nonresidue when is odd.

Gauss' Lemma is the special case

$\displaystyle 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

elements, and identify $\mathbbmss{F}_p$ with the set $\{0,1,\ldots,p-1\}$ , with its addition and multiplication mod

Proposition 2: Let 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 be the number of elements $k\in S$ such that $kn\notin S$ . Then

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

Proof: If

and

are distinct elements of

, we cannot have $an=\pm bn$ , in view of the hypothesis on

. Therefore

$\displaystyle \prod_{a\in S}an=(-1)^{u(n)}\prod_{a\in S}a.$

On the left we have

$\displaystyle n^{(p-1)/2}\prod_{a\in S}a=\left(\frac{n}{p}\right)\prod_{a\in S}a$

by Euler's criterion. So

$\displaystyle \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 :

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

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

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

$\displaystyle S=\{1,2,\ldots,(p-1)/2\}\;,$

the set

$\displaystyle \{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:

$\displaystyle \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.

"Gauss' lemma" is owned by drini. [ full author list (3) | owner history (2) ]

(view preamble)

See Also: Euler's criterion, Zolotarev's lemma

Log in to rate this entry.
(view current ratings)

Cross-references: degree, polynomial, primitive root, trigonometric identity, square, product, Euler's criterion, hypothesis, subset, multiplication, addition, field, quadratic nonresidue, even, Legendre symbol, residues, positive, number, multiple, integer, prime, odd, quadratic residues
There are 6 references to this entry.

This is version 11 of Gauss' lemma, born on 2002-02-14, modified 2006-12-22.
Object id is 1955, canonical name is GaussLemma.
Accessed 7290 times total.

Classification:

AMS MSC:

11A15 (Number theory :: Elementary number theory :: Power residues, reciprocity)

Pending Errata and Addenda

None.[ View all 5 ]

Discussion

forum policy

No messages.

Interact