Gauss's lemma (number theory) explained

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

a, 2 a, 3 a, ... , (p -1)/(2) a 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

\left( (a)/(p) \right) = ( -1 ) ^{n,} where \left( (a)/(p) \right) 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

\left( (7)/(11) \right) = ( -1 ) ^{3} = -1 . This is indeed correct, because 7 is not a quadratic residue modulo 11.

The above sequence of residues

7, 3, 10, 6, 2may 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

Z = a ⋅ 2 a ⋅ 3 a ⋅ … ⋅ (p -1)/(2) a modulo p in two different ways. On one hand it is equal toZ = a ^{(p-1)/2} \left( 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ (p -1)/(2) \right)

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

|x| = \begin{cases} x & if 1 \leq x \leq (p -1)/(2 ,) \ p - x & if (p +1)/(2) \leq x \leq p -1 . \end{cases} Since counts those multiples which are in the latter range, and since for those multiples, is in the first range, we haveZ = ( -1 ) ^{n} \left(|a| ⋅ | 2 a| ⋅ | 3 a| ⋅ … … \left| (p -1)/(2) a\right|\right). Now observe that the values are distinct for . Indeed, we have\begin{align} |ra| &\equiv |sa| &\pmod{p} \\ ra &\equiv \pm sa &\pmod{p} \\ r &\equiv \pm s &\pmod{p} \end{align} 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,

Z = ( -1 ) ^{n} \left( 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ (p -1)/(2 \right).) Comparing with our first evaluation, we may cancel out the nonzero factor1 ⋅ 2 ⋅ 3 ⋅ … ⋅ (p -1)/(2) and we are left witha ^{(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 \left ( (a)/(p) \right ) .

Generalization

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

Let

I \subset( Z / p Z ) ^{x} be a set such that ( Z / p Z ) ^{x} is the disjoint union of I and - I = \{ - i: i \in I\} .

Then

\left( (a)/(p) \right) = ( -1 ) ^{t} , where t = \#\{j \in I: a j \in - I\} .^[1]

In the original statement,

I = \{ 1 , 2 , ... , (p -1)/(2 \}) .

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

\left( (a)/(p) \right) = \prod ^{(p -1 )/ 2} _{n =1} (\sin{( 2 \pi an/p))/() },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

\left( (p)/(q) \right) =sgn \prod ^{(q -1)/(2)} _{i =1} \prod ^{(p -1)/(2)} _{k =1} \left( (k)/(- p) (i)/(q) \right).

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

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

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

l{O} _{k,} and let ak{p} \subset l{O} _{k} be a prime ideal. The ideal norm N ak{p} of ak{p} is defined as the cardinality of the residue class ring. Since ak{p} is prime this is a finite field l{O} _{k} / ak{p} , so the ideal norm is N ak{p} = | l{O} _{k} / ak{p}| .\zeta _{n\inl{O}} _{k,} and that and ak{p} are coprime (i.e. n\not\in ak{p} ). Then no two distinct th roots of unity can be congruent modulo ak{p} .

This can be proved by contradiction, beginning by assuming that

\zeta ^{s} _{n} mod ak{p} , . Let such that \zeta ^{t\equiv} _{n} 1 mod ak{p} , and . From the definition of roots of unity, x ^{n -1= (x -1 )(x - \zeta} _{n)(x - \zeta} ^{n -1} ^{n} ), and dividing by gives x ^{n-1} + x ^{n-2} +... + x + 1 = (x - \zeta _{n)(x-\zeta} ^{n -1} ^{n} ).

Letting and taking residues mod

ak{p} ,n\equiv( 1- \zeta _{n)(1-\zeta} ^{n -1} ^{n} )\pmod{ ak{p}}.

Since and

ak{p} are coprime, n\not\equiv 0 mod ak{p}, 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

l{O} _{k} / ak{p} containing the powers of are a subgroup of order of its (multiplicative) group of units, ( l{O} ^{x} _{k/ ak{p})} = l{O} _{k} / ak{p}- \{ 0 \}. Therefore, the order of ( l{O} ^{x} _{k/ ak{p})} is a multiple of, and \begin{align} N ak{p} & = | l{O} _{k} / ak{p}| \\ & = \left |( l{O} _{k} / ak{p} ) ^{x} \right| + 1 \\ &\equiv 1 \pmod{n}. \end{align}

There is an analogue of Fermat's theorem in

l{O} _{k} . If \alpha \in l{O} _{k} for \alpha\not\in ak{p} , then \alpha ^{N} -1 }\equiv 1 \pmod{ ak{p} }, and since N ak{p} \equiv 1 mod,\alpha ^{(N ak{p)/(-1)} {n}}\equiv \zeta ^{s\pmod{ ak{p} }} _{n} is well-defined and congruent to a unique th root of unity ζ_n^s.

This root of unity is called the th-power residue symbol for

l{O} _{k,} and is denoted by\begin{align} \left( (\alpha)/(ak{p) }\right) _{n} & = \zeta ^{s} _{n} \\ &\equiv \alpha ^{(N ak{p)/(-1)} {n}}\pmod{ ak{p}}. \end{align}

It can be proven that

\left( (\alpha)/(ak{p) }\right) _{n=} 1 if and only if there is an η \in l{O} _{k} such that mod ak{p} .

1/n systems

Let

\mu _{n} = \{ 1 ,\zeta _{n,\zeta} ^{n -1} ^{n} \} be the multiplicative group of the th roots of unity, and let A = \{a _{1,} a _{2,...,a} _{m\}} be representatives of the cosets of ( l{O} _{k} / ak{p}) ^{x /\mu} _{n.} Then is called a system mod ak{p}.

In other words, there are

mn = N ak{p} -1 numbers in the set A\mu = \{ a _{i} \zeta ^{j :} _{n} 1 \le i \le m, 0 \le j \le n -1 \}, and this set constitutes a representative set for ( l{O} _{k} / ak{p}) ^{x .}

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

( l{O} _{k} / ak{p}) ^{x .} Pick any a _{1\in} M and remove the numbers congruent to a _{1,} a _{1\zeta} _{n,} a _{1\zeta} ^{2 ,} ^{n} ... , a _{1\zeta} ^{n -1} ^{n} from . Pick from and remove the numbers congruent to a _{2,} a _{2\zeta} _{n,} a _{2\zeta} ^{2 ,} ^{n} ... , a _{2\zeta} ^{n -1} ^{n} Repeat until is exhausted. Then is a system mod ak{p}.

The lemma for nth powers

Gauss's lemma may be extended to the th power residue symbol as follows. Let

\zeta _{n\in} l{O} _{k} be a primitive th root of unity, ak{p} \subset l{O} _{k} a prime ideal, \gamma \in l{O} _{k,} n\gamma\not\in ak{p}, (i.e. ak{p} is coprime to both and) and let be a system mod ak{p}.

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

\gamma a _{i} \equiv \zeta ^{b(i)} _{n} a _{\pi(i)} \pmod{ ak{p}}, and the th-power residue symbol is given by the formula\left( (\gamma)/(ak{p) }\right) _{n} = \zeta ^{b( 1 ) + b( 2 ) +...+ b(m)} _{n} .

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.

\gamma a _{i} \equiv \zeta ^{r} _{n} a _{p} \pmod{ ak{p}} and\gamma a _{j} \equiv \zeta ^{s} _{n} a _{p} \pmod{ ak{p}}. Then\zeta ^{s - r} _{n} \gamma a _{i} \equiv \zeta ^{s} _{n} a _{p} \equiv \gamma a _{j\pmod{ak{p}}} Because and ak{p} are coprime both sides can be divided by, giving \zeta ^{s - r} _{n} a _{i} \equiv a _{j\pmod{ak{p}},} 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,

\begin{align} (\gamma a _{1)(\gamma} a _{2)...(\gamma} a _{m)} & = \gamma ^{(N ak{p)/(-1)} {n}} a _{1} a _{2...} a _{m} \\ &\equiv \left( (\gamma)/(ak{p) }\right) _{n} a _{1} a _{2...} a _{m} \pmod{ ak{p}}, \end{align} and on the other hand, since is a permutation,\begin{align} (\gamma a _{1)(\gamma} a _{2)...(\gamma} a _{m)} &\equiv {\zeta ^{b( 1 )} _{n} a _{\pi(1)} } \dots &\pmod\\&\equiv\zeta_n^a_ a_\dots a_&\pmod\\&\equiv\zeta_n^ a_1 a_2\dots a_m&\pmod,\endso\left( (\gamma)/(ak{p) }\right) _{n} a _{1} a _{2...} a _{m} \equiv \zeta ^{b( 1 ) + b( 2 ) +...+ b(m)} _{n} a _{1} a _{2...} a _{m \pmod{ak{p}},} and since for all, and ak{p} are coprime, can be cancelled from both sides of the congruence,\left( (\gamma)/(ak{p) }\right) _{n} \equiv \zeta ^{b( 1 ) + b( 2 ) +...+ b(m)} _{n} \pmod{ ak{p}}, and the theorem follows from the fact that no two distinct th roots of unity can be congruent (mod ak{p} ).

Relation to the transfer in group theory

Let be the multiplicative group of nonzero residue classes in, and let be the subgroup . Consider the following coset representatives of in,

1 , 2 , 3 , ... , (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 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

Notes and References

1. Book: Kremnizer, Kobi. Lectures in number theory 2022.