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


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


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


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


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


On the left we have


by Euler’s criterion. So


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


the set


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:


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