Gauss’ lemma on quadratic residues is:
where 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
Proposition 2: Let be a subset of such that or , but not both, for any . For let be the number of elements such that . Then
Proof: If and are distinct elements of , we cannot have , in view of the hypothesis on . 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 :
The condition on can also be stated like this: for any square , there is a unique such that . Apart from the usual choice
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 root, or the fact that a polynomial over has no more zeros than its degree.
|Date of creation||2013-03-22 12:19:46|
|Last modified on||2013-03-22 12:19:46|
|Last modified by||drini (3)|