Gauss’ lemma


Gauss’ lemma on quadratic residuesMathworldPlanetmath is:

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

{n,2n,3n,,p-12n}

whose least positive residuesDlmfMathworld, modulo p, are greater than p/2. Then

(np)=(-1)u

where (np) is the Legendre symbolDlmfMathworldPlanetmath.

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,,p-12}

of the slightly more general statement below. Write 𝔽p for the field of p elements, and identify 𝔽p with the set {0,1,,p-1}, with its addition and multiplication mod p.

Proposition 2: Let S be a subset of 𝔽p* such that xS or -xS, but not both, for any x𝔽p*. For n𝔽p* let u(n) be the number of elements kS such that knS. Then

(np)=(-1)u(n).

Proof: If a and b are distinct elements of S, we cannot have an=±bn, in view of the hypothesis on S. Therefore

aSan=(-1)u(n)aSa.

On the left we have

n(p-1)/2aSa=(np)aSa

by Euler’s criterion. So

(np)aSa=(-1)u(n)aSa

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:

(-1p)={1 if p1(mod4)-1 if p-1(mod4)
(2p)={1 if p±1(mod8)-1 if p±3(mod8)

The condition on S can also be stated like this: for any square x2𝔽p*, there is a unique yS such that x2=y2. Apart from the usual choice

S={1,2,,(p-1)/2},

the set

{2,4,,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:

(np)=aSsin(2πan/p)sin(2π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 rootMathworldPlanetmath, or the fact that a polynomialPlanetmathPlanetmath over 𝔽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