Gauss's lemma (number theory)

From Wikipedia, the free encyclopedia

This article is about Gauss's lemma in number theory. Gauss's lemma (polynomial) concerns factoring polynomials.

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] of quadratic reciprocity and he proved it again in his fifth proof (1818).[2]

Contents

[edit] Statement of the lemma

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

Consider the integers

a, 2a, 3a, \dots, \frac{p-1}{2}a

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

\left(\frac{a}{p}\right) = (-1)^n

where (a/p) is the Legendre symbol.

[edit] Example

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

\left(\frac{7}{11}\right) = (-1)^3 = -1.

This is indeed correct, because 7 is not a quadratic residue modulo 11.

[edit] Proof

A fairly simple proof[3] of the lemma, reminiscent of one of the simplest proofs of Fermat's little theorem, can be obtained by evaluating the product

Z = a \cdot 2a \cdot 3a \cdot \cdots \cdot \frac{p-1}2 a

modulo p in two different ways. On one hand it is equal to

Z = a^{(p-1)/2} \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 \right)

The second evaluation takes more work. If x is a nonzero residue modulo p, let us define the "absolute value" of x to be

|x| = \begin{cases} x & \mbox{if } 1 \leq x \leq \frac{p-1}2, \\ -x & \mbox{if } \frac{p+1}2 \leq x \leq p-1. \end{cases}

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

Z = (-1)^n \left(|a| \cdot |2a| \cdot |3a| \cdot \cdots \cdots \left|\frac{p-1}2 a\right|\right).

Now observe that the values |ra| are distinct for r = 1, 2, ..., (p−1)/2. Indeed, if |ra| = |sa|, then ra = ±sa, and therefore r = ±s (because a is invertible modulo p), so r = s because they are both in the range 1 ≤ r ≤ (p−1)/2. But there are exactly (p−1)/2 of them, so they must just be some rearrangement of the integers 1, 2, ..., (p−1)/2. Therefore

Z = (-1)^n \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2\right).

Comparing with our first evaluation, we may cancel out the nonzero factor

1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2

and we are left with

a(p − 1) / 2 = ( − 1)n.

This is the desired result, because by Euler's criterion the left hand side is just an alternative expression for the Legendre symbol (a/p).

[edit] Applications

Gauss's lemma is used in many[4][5], but by no means all, of the known proofs of quadratic reciprocity.

For example, Eisenstein[6] used Gauss's lemma to prove that if p is an odd prime then

\left(\frac{a}{p}\right)=\prod_{n=1}^{(p-1)/2}\frac{\sin{(2\pi an/p)}}{\sin{(2\pi n/p)}},

and used this formula to prove quadratic reciprocity, (and, by using elliptic rather than circular functions, to prove the cubic and quartic reciprocity laws[7])

Kronecker[8] used the lemma to show that

\left(\frac{p}{q}\right)=\sgn\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right).

Switching p and q immediately gives quadratic reciprocity.

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

\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1\text{ if }p\equiv 1\pmod {4}\\-1\text{ if }p\equiv -1\pmod {4}\end{cases}
\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} 1\text{ if }p\equiv \pm 1\pmod {8}\\-1\text{ if }p\equiv \pm 3\pmod {8}\end{cases}

[edit] Relation to the transfer in group theory

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,

1, 2, 3, \dots, \frac{p-1}{2}.

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

\phi : G \to H,

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.

[edit] See also

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

[edit] Notes

  1. ^ "Neuer Beweis eines arithmetischen Satzes"; pp 458-462 of Untersuchungen uber hohere Arithmetik
  2. ^ "Neue Beweise und Erweiterungen des Fundalmentalsatzes in der Lehre von den quadratischen Reste"; pp 496-501 of Untersuchungen uber hohere Arithmetik
  3. ^ Any textbook on elementary number theory will have a proof. The one here is basically Gauss's from "Neuer Beweis eines arithnetischen Satzes"; pp 458-462 of Untersuchungen uber hohere Arithmetik
  4. ^ Lemmermeyer, ch. 1
  5. ^ Lemmermeyer, p. 9 "like most of the simplest proofs [ of QR], [Gauss's] 3 and 5 rest on what we now call Gauss's Lemma
  6. ^ Lemmermeyer, p. 236, Prop 8.1 (1845)
  7. ^ Lemmermeyer, ch. 8
  8. ^ Lemmermeyer, ex. 1.34 (The year isn't clear because K. published 8 proofs, several based on Gauss's lemma, between 1875 and 1889)

[edit] References

  • Gauss, Carl Friedrich & Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disqusitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8