|
|
|
|
|
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
whose least positive residues, modulo , are greater than . Then
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
of the slightly more general statement below. Write
for the field of elements, and identify
with the set
, with its addition and multiplication mod .
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
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 root, or the fact that a polynomial over
has no more zeros than its degree.
|
"Gauss' lemma" is owned by drini. [ full author list (3) | owner history (2) ]
|
|
(view preamble)
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
|
|
|
|
|
|
|
|
|
|
|