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.
Correspondingly Gauss's lemma predicts that This is indeed correct, because 7 is not a quadratic residue modulo 11.
The above sequence of residues may also be written 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 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.
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
By using elliptic rather than circular functions, he proved the cubic and quartic reciprocity laws.[3]: Ch.
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" Generalizations of Gauss's lemma can be used to compute higher power residue symbols.
In his second monograph on biquadratic reciprocity,[4]: §§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.[3]: Ch.
8 Let k be an algebraic number field with ring of integers
is defined as the cardinality of the residue class ring.
Then no two distinct nth roots of unity can be congruent modulo
, and 0 < t < n. From the definition of roots of unity, and dividing by x − 1 gives Letting x = 1 and taking residues mod
Therefore, the assumption that two distinct roots are congruent is false.
containing the powers of ζn are a subgroup of order n of its (multiplicative) group of units,
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
be the multiplicative group of the nth roots of unity, and let
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
Gauss's lemma may be extended to the nth power residue symbol as follows.[3]: Prop.
Then for each i, 1 ≤ i ≤ m, 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.
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}.
are coprime, a1a2…am 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
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.