# 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

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

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.

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

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

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

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

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

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

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

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

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

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.

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.