Gauss's lemma (number theory)
Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity. It made its first appearance in Carl Friedrich Gauss's third proof (1808) of quadratic reciprocity and he proved it again in his fifth proof (1818). Statement of the lemma 
For any odd prime  let  be an integer that is coprime to . Consider the integers

and their least positive residues modulo . These residues are all distinct, so there are ( of them. Let  be the number of these residues that are greater than . Then

where  is the Legendre symbol. Example 
Taking  = 11 and  = 7, the relevant sequence of integers is
 7, 14, 21, 28, 35. After reduction modulo 11, this sequence becomes
 7, 3, 10, 6, 2. Three of these integers are larger than 11/2 (namely 6, 7 and 10), so  = 3. Correspondingly Gauss's lemma predicts that
 
This is indeed correct, because 7 is not a quadratic residue modulo 11. The above sequence of residues
 7, 3, 10, 6, 2
may also be written
 −4, 3, −1, −5, 2. In this form, the integers larger than 11/2 appear as negative numbers. It is also apparent that the absolute values of the residues are a permutation of the residues
 1, 2, 3, 4, 5. Proof 
A fairly simple proof, reminiscent of one of the simplest proofs of Fermat's little theorem, can be obtained by evaluating the product
 
modulo p in two different ways. On one hand it is equal to
 

The second evaluation takes more work. If  is a nonzero residue modulo , let us define the "absolute value" of  to be
 
Since  counts those multiples  which are in the latter range, and since for those multiples,  is in the first range, we have
 
Now observe that the values  are distinct for . Indeed, we have

because  is coprime to . This gives  = , since  and  are positive least residues. But there are exactly  of them, so their values are a rearrangement of the integers . Therefore,
 
Comparing with our first evaluation, we may cancel out the nonzero factor
 
and we are left with
 
This is the desired result, because by Euler's criterion the left hand side is just an alternative expression for the Legendre symbol . Generalization 
For any odd prime  let  be an integer that is coprime to . Let  be a set such that  is the disjoint union of  and . Then , where . In the original statement, . The proof is almost the same. Applications 
Gauss's lemma is used in many, but by no means all, of the known proofs of quadratic reciprocity. For example, Gotthold Eisenstein used Gauss's lemma to prove that if  is an odd prime then

and used this formula to prove quadratic reciprocity. By using elliptic rather than circular functions, he proved the cubic and quartic reciprocity laws. Leopold Kronecker used the lemma to show that

Switching  and  immediately gives quadratic reciprocity. It is also used in what are probably the simplest proofs of the "second supplementary law"

Higher powers

Generalizations of Gauss's lemma can be used to compute higher power residue symbols. In his second monograph on biquadratic reciprocity, Gauss used a fourth-power lemma to derive the formula for the biquadratic character of  in , the ring of Gaussian integers. Subsequently, Eisenstein used third- and fourth-power versions to prove cubic and quartic reciprocity. nth power residue symbol

Let k be an algebraic number field with ring of integers  and let  be a prime ideal. The ideal norm  of  is defined as the cardinality of the residue class ring. Since  is prime this is a finite field , so the ideal norm is . Assume that a primitive th root of unity  and that  and  are coprime (i.e. ). Then no two distinct th roots of unity can be congruent modulo . This can be proved by contradiction, beginning by assuming that  mod , . Let  such that  mod , and . From the definition of roots of unity, 

and dividing by  gives 

Letting  and taking residues mod ,

Since   and  are coprime,  mod  but under the assumption, one of the factors on the right must be zero. Therefore, the assumption that two distinct roots are congruent is false. Thus the residue classes of  containing the powers of  are a subgroup of order  of its (multiplicative) group of units,  Therefore, the order of  is a multiple of , and 

There is an analogue of Fermat's theorem in . If  for , then 

and since  mod ,

is well-defined and congruent to a unique th root of unity ζns. This root of unity is called the th-power residue symbol for  and is denoted by

It can be proven that

if and only if there is an  such that  mod . 1/n systems
Let  be the multiplicative group of the th roots of unity, and let  be representatives of the cosets of  Then  is called a  system mod 

In other words, there are  numbers in the set  and this set constitutes a representative set for 

The numbers , used in the original version of the lemma, are a 1/2 system (mod ). Constructing a  system is straightforward: let  be a representative set for  Pick any  and remove the numbers congruent to  from . Pick   from  and remove the numbers congruent to  Repeat until  is exhausted. Then  is a  system mod

The lemma for nth powers
Gauss's lemma may be extended to the th power residue symbol as follows. Let  be a primitive th root of unity,  a prime ideal,  (i.e. is coprime to both  and ) and let  be a   system mod 

Then for each , , there are integers , unique (mod ), and , unique (mod ),  such that

and the th-power residue symbol is given by the formula

The classical lemma for the quadratic Legendre symbol is the special case , , ,  if ,  if . Proof
The proof of the th-power lemma uses the same ideas that were used in the proof of the quadratic lemma. The existence of the integers  and , and their uniqueness  (mod ) and (mod ), respectively, come from the fact that  is a representative set. Assume that  =  = , i.e. and

Then

Because  and  are coprime both sides can be divided by , giving 

which, since  is a  system, implies  and , showing that  is a permutation of the set . Then on the one hand, by the definition of the power residue symbol,

and on the other hand, since  is a permutation,

so

and since for all ,  and  are coprime,  can be cancelled from both sides of the congruence,

and the theorem follows from the fact that no two distinct th roots of unity can be congruent (mod ). Relation to the transfer in group theory 

Let  be the multiplicative group of nonzero residue classes in , and let  be the subgroup {+1, −1}. Consider the following coset representatives of  in ,

Applying the machinery of the transfer to this collection of coset representatives, we obtain the transfer homomorphism

which turns out to be the map that sends  to , where  and  are as in the statement of the lemma. Gauss's lemma may then be viewed as a computation that explicitly identifies this homomorphism as being the quadratic residue character. See also 

 Zolotarev's lemma

References

Articles containing proofs
Lemmas in number theory
Modular arithmetic
Quadratic residue
Squares in number theory