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)[1]:458–462 of quadratic reciprocity and he proved it again in his fifth proof (1818).[1]:496–501

Statement of the lemmaEdit

For any odd prime p let a be an integer that is coprime to p.

Consider the integers

 

and their least positive residues modulo p. (These residues are all distinct, so there are (p − 1)/2 of them.)

Let n be the number of these residues that are greater than p/2. Then

 

where   is the Legendre symbol.

ExampleEdit

Taking p = 11 and a = 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 n = 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.

ProofEdit

A fairly simple proof,[1]:458–462 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 x is a nonzero residue modulo p, let us define the "absolute value" of x to be

 

Since n counts those multiples ka which are in the latter range, and since for those multiples, ka is in the first range, we have

 

Now observe that the values |ra| are distinct for r = 1, 2, …, (p − 1)/2. Indeed, we have

 

because a is coprime to p.

This gives r = s, since r and s are positive least residues. But there are exactly (p − 1)/2 of them, so their values are a rearrangement of the integers 1, 2, …, (p − 1)/2. 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  .

ApplicationsEdit

Gauss's lemma is used in many,[2]:Ch. 1[2]:9 but by no means all, of the known proofs of quadratic reciprocity.

For example, Gotthold Eisenstein[2]:236 used Gauss's lemma to prove that if p 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.[2]:Ch. 8

Leopold Kronecker[2]:Ex. 1.34 used the lemma to show that

 

Switching p and q immediately gives quadratic reciprocity.

It is also used in what are probably the simplest proofs of the "second supplementary law"

 

Higher powersEdit

Generalizations of Gauss's lemma can be used to compute higher power residue symbols. In his second monograph on biquadratic reciprocity,[3]:§§69–71 Gauss used a fourth-power lemma to derive the formula for the biquadratic character of 1 + i in Z[i], the ring of Gaussian integers. Subsequently, Eisenstein used third- and fourth-power versions to prove cubic and quartic reciprocity.[2]:Ch. 8

nth power residue symbolEdit

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 nth root of unity   and that n and   are coprime (i.e.  ). Then no two distinct nth roots of unity can be congruent modulo  .

This can be proved by contradiction, beginning by assuming that   mod  , 0 < r < sn. Let t = sr such that   mod  , and 0 < t < n. From the definition of roots of unity,

 

and dividing by x − 1 gives

 

Letting x = 1 and taking residues mod  ,

 

Since n 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 ζn are a subgroup of order n of its (multiplicative) group of units,   Therefore, the order of   is a multiple of n, and

 

There is an analogue of Fermat's theorem in  . If   for  , then[2]:Ch. 4.1

 

and since   mod n,

 

is well-defined and congruent to a unique nth root of unity ζns.

This root of unity is called the nth-power residue symbol for   and is denoted by

 

It can be proven that[2]:Prop. 4.1

 

if and only if there is an   such that αηn mod  .

1/n systemsEdit

Let   be the multiplicative group of the nth roots of unity, and let   be representatives of the cosets of   Then A is called a 1/n system mod  [2]:Ch. 4.2

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

The numbers 1, 2, … (p − 1)/2, used in the original version of the lemma, are a 1/2 system (mod p).

Constructing a 1/n system is straightforward: let M be a representative set for   Pick any   and remove the numbers congruent to   from M. Pick a2 from M and remove the numbers congruent to   Repeat until M is exhausted. Then {a1, a2, … am} is a 1/n system mod  

The lemma for nth powersEdit

Gauss's lemma may be extended to the nth power residue symbol as follows.[2]:Prop. 4.3 Let   be a primitive nth root of unity,   a prime ideal,   (i.e.   is coprime to both γ and n) and let A = {a1, a2, …, am} be a 1/n system mod  

Then for each i, 1 ≤ im, there are integers π(i), unique (mod m), and b(i), unique (mod n), such that

 

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

 

The classical lemma for the quadratic Legendre symbol is the special case n = 2, ζ2 = −1, A = {1, 2, …, (p − 1)/2}, b(k) = 1 if ak > p/2, b(k) = 0 if ak < p/2.

ProofEdit

The proof of the nth-power lemma uses the same ideas that were used in the proof of the quadratic lemma.

The existence of the integers π(i) and b(i), and their uniqueness (mod m) and (mod n), respectively, come from the fact that is a representative set.

Assume that π(i) = π(j) = p, i.e.

 

and

 

Then

 

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

 

which, since A is a 1/n system, implies s = r and i = j, showing that π is a permutation of the set {1, 2, …, m}.

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 1 ≤ im, ai and   are coprime, a1a2am can be cancelled from both sides of the congruence,

 

and the theorem follows from the fact that no two distinct nth roots of unity can be congruent (mod  ).

Relation to the transfer in group theoryEdit

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

 

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 a to (−1)n, where a and n 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 alsoEdit

Two other characterizations of squares modulo a prime are Euler's criterion and Zolotarev's lemma.

ReferencesEdit

  1. ^ a b c Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (in German), translated by H. Maser (2nd ed.), New York: Chelsea, ISBN 0-8284-0191-8
  2. ^ a b c d e f g h i j Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, ISBN 3-540-66957-4
  3. ^ Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, 7, Göttingen: Comment. Soc. regiae sci