Gauss's lemma (number theory)

Template:Short description Template:About 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)Template:Rp of quadratic reciprocity and he proved it again in his fifth proof (1818).Template:Rp

Statement of the lemma

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

Consider the integers

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

and their least positive residues modulo Template:Math. These residues are all distinct, so there are (Template:Math of them.

Let Template:Math be the number of these residues that are greater than Template:Math. Then

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

where $\left(\frac{a}{p}\right)$ is the Legendre symbol.

Example

Taking Template:Math = 11 and Template:Math = 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 Template:Math = 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.

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.

Proof

A fairly simple proof,Template:Rp 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}(1\cdot 2\cdot 3\cdot \cdots \cdot \frac{p-1}{2})$

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

$|x|=\{\begin{array}{cc}x& \text{if }1\le x\le \frac{p-1}{2},\\ p-x& \text{if }\frac{p+1}{2}\le x\le p-1.\end{array}$

Since Template:Math counts those multiples Template:Math which are in the latter range, and since for those multiples, Template:Math is in the first range, we have

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

Now observe that the values Template:Math are distinct for Template:Math. Indeed, we have

$\begin{array}{ccc}|ra|& \equiv |sa|& (\mathrm{mod}p)\\ ra& \equiv \pm sa& (\mathrm{mod}p)\\ r& \equiv \pm s& (\mathrm{mod}p)\end{array}$

because Template:Math is coprime to Template:Math.

This gives Template:Math = Template:Math, since Template:Math and Template:Math are positive least residues. But there are exactly Template:Math of them, so their values are a rearrangement of the integers Template:Math. Therefore,

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

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 $\left(\frac{a}{p}\right)$.

Generalization

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

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

Then $\left(\frac{a}{p}\right)=(-1{)}^t$, where $t=\mathrm{\#}\{j\in I:aj\in -I\}$.

In the original statement, $I=\{1,2,\dots ,\frac{p-1}{2}\}$.

The proof is almost the same.

Applications

Gauss's lemma is used in many,Template:RpTemplate:Rp but by no means all, of the known proofs of quadratic reciprocity.

For example, Gotthold EisensteinTemplate:Rp used Gauss's lemma to prove that if Template:Math 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. By using elliptic rather than circular functions, he proved the cubic and quartic reciprocity laws.Template:Rp

Leopold KroneckerTemplate:Rp used the lemma to show that

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

Switching Template:Math and Template:Math immediately gives quadratic reciprocity.

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

$\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}=\{\begin{array}{c}+1\text{ if }p\equiv \pm 1(\mathrm{mod}8)\\ -1\text{ if }p\equiv \pm 3(\mathrm{mod}8)\end{array}$

Higher powers

Generalizations of Gauss's lemma can be used to compute higher power residue symbols. In his second monograph on biquadratic reciprocity,Template:Rp Gauss used a fourth-power lemma to derive the formula for the biquadratic character of Template:Math in Template:Math, the ring of Gaussian integers. Subsequently, Eisenstein used third- and fourth-power versions to prove cubic and quartic reciprocity.Template:Rp

nth power residue symbol

Template:Main article Let k be an algebraic number field with ring of integers ${𝒪}_k,$ and let $𝔭\subset {𝒪}_k$ be a prime ideal. The ideal norm $\mathrm{N}𝔭$ of $𝔭$ is defined as the cardinality of the residue class ring. Since $𝔭$ is prime this is a finite field ${𝒪}_k/𝔭$, so the ideal norm is $\mathrm{N}𝔭=|{𝒪}_k/𝔭|$.

Assume that a primitive Template:Mathth root of unity ${\zeta }_n\in {𝒪}_k,$ and that Template:Math and $𝔭$ are coprime (i.e. $n\in ̸𝔭$). Then no two distinct Template:Mathth roots of unity can be congruent modulo $𝔭$.

This can be proved by contradiction, beginning by assuming that ${\zeta }_n^r\equiv {\zeta }_n^s$ mod $𝔭$, Template:Math. Let Template:Math such that ${\zeta }_n^t\equiv 1$ mod $𝔭$, and Template:Math. From the definition of roots of unity,

$x^n-1=(x-1)(x-{\zeta }_n)(x-{\zeta }_n^2)\dots (x-{\zeta }_n^{n-1}),$

and dividing by Template:Math gives

$x^{n-1}+x^{n-2}+\dots +x+1=(x-{\zeta }_n)(x-{\zeta }_n^2)\dots (x-{\zeta }_n^{n-1}).$

Letting Template:Math and taking residues mod $𝔭$,

$n\equiv (1-{\zeta }_n)(1-{\zeta }_n^2)\dots (1-{\zeta }_n^{n-1})(\mathrm{mod}𝔭).$

Since Template:Math and $𝔭$ are coprime, $n\equiv ̸0$ 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 ${𝒪}_k/𝔭$ containing the powers of Template:Math are a subgroup of order Template:Math of its (multiplicative) group of units, $({𝒪}_k/𝔭{)}^{\times }={𝒪}_k/𝔭-\{0\}.$ Therefore, the order of $({𝒪}_k/𝔭{)}^{\times }$ is a multiple of Template:Math, and

$\begin{array}{cc}\mathrm{N}𝔭& =|{𝒪}_k/𝔭|\\ & =|({𝒪}_k/𝔭{)}^{\times }|+1\\ & \equiv 1(\mathrm{mod}n).\end{array}$

There is an analogue of Fermat's theorem in ${𝒪}_k$. If $\alpha \in {𝒪}_k$ for $\alpha \in ̸𝔭$, thenTemplate:Rp

${\alpha }^{\mathrm{N}𝔭-1}\equiv 1(\mathrm{mod}𝔭),$

and since $\mathrm{N}𝔭\equiv 1$ mod Template:Math,

${\alpha }^{\frac{\mathrm{N}𝔭-1}{n}}\equiv {\zeta }_n^s(\mathrm{mod}𝔭)$

is well-defined and congruent to a unique Template:Mathth root of unity ζ_n^s.

This root of unity is called the Template:Mathth-power residue symbol for ${𝒪}_k,$ and is denoted by

$\begin{array}{cc}{\left(\frac{\alpha }{𝔭}\right)}_n& ={\zeta }_n^s\\ & \equiv {\alpha }^{\frac{\mathrm{N}𝔭-1}{n}}(\mathrm{mod}𝔭).\end{array}$

It can be proven thatTemplate:Rp

${\left(\frac{\alpha }{𝔭}\right)}_n=1$

if and only if there is an $\eta \in {𝒪}_k$ such that Template:Math mod $𝔭$.

1/n systems

Let ${\mu }_n=\{1,{\zeta }_n,{\zeta }_n^2,\dots ,{\zeta }_n^{n-1}\}$ be the multiplicative group of the Template:Mathth roots of unity, and let $A=\{a_1,a_2,\dots ,a_m\}$ be representatives of the cosets of $({𝒪}_k/𝔭{)}^{\times }/{\mu }_n.$ Then Template:Math is called a Template:Math system mod $𝔭.$Template:Rp

In other words, there are $mn=\mathrm{N}𝔭-1$ numbers in the set $A\mu =\{a_i{\zeta }_n^j:1\le i\le m,0\le j\le n-1\},$ and this set constitutes a representative set for $({𝒪}_k/𝔭{)}^{\times }.$

The numbers Template:Math, used in the original version of the lemma, are a 1/2 system (mod Template:Math).

Constructing a Template:Math system is straightforward: let Template:Math be a representative set for $({𝒪}_k/𝔭{)}^{\times }.$ Pick any $a_1\in M$ and remove the numbers congruent to $a_1,a_1{\zeta }_n,a_1{\zeta }_n^2,\dots ,a_1{\zeta }_n^{n-1}$ from Template:Math. Pick Template:Math from Template:Math and remove the numbers congruent to $a_2,a_2{\zeta }_n,a_2{\zeta }_n^2,\dots ,a_2{\zeta }_n^{n-1}$ Repeat until Template:Math is exhausted. Then Template:Math is a Template:Math system mod $𝔭.$

The lemma for nth powers

Gauss's lemma may be extended to the Template:Mathth power residue symbol as follows.Template:Rp Let ${\zeta }_n\in {𝒪}_k$ be a primitive Template:Mathth root of unity, $𝔭\subset {𝒪}_k$ a prime ideal, $\gamma \in {𝒪}_k,n\gamma \in ̸𝔭,$ (i.e. $𝔭$ is coprime to both Template:Math and Template:Math) and let Template:Math be a Template:Math system mod $𝔭.$

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

$\gamma a_i\equiv {\zeta }_n^{b(i)}{a}_{\pi (i)}(\mathrm{mod}𝔭),$

and the Template:Mathth-power residue symbol is given by the formula

${\left(\frac{\gamma }{𝔭}\right)}_n={\zeta }_n^{b(1)+b(2)+\dots +b(m)}.$

The classical lemma for the quadratic Legendre symbol is the special case Template:Math, Template:Math, Template:Math, Template:Math if Template:Math, Template:Math if Template:Math.

Proof

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

The existence of the integers Template:Math and Template:Math, and their uniqueness (mod Template:Math) and (mod Template:Math), respectively, come from the fact that Template:Math is a representative set.

Assume that Template:Math = Template:Math = Template:Math, i.e.

$\gamma a_i\equiv {\zeta }_n^r{a}_p(\mathrm{mod}𝔭)$

and

$\gamma a_j\equiv {\zeta }_n^s{a}_p(\mathrm{mod}𝔭).$

Then

${\zeta }_n^{s-r}\gamma a_i\equiv {\zeta }_n^s{a}_p\equiv \gamma a_j(\mathrm{mod}𝔭)$

Because Template:Math and $𝔭$ are coprime both sides can be divided by Template:Math, giving

${\zeta }_n^{s-r}{a}_i\equiv a_j(\mathrm{mod}𝔭),$

which, since Template:Math is a Template:Math system, implies Template:Math and Template:Math, showing that Template:Math is a permutation of the set Template:Math.

Then on the one hand, by the definition of the power residue symbol,

$\begin{array}{cc}(\gamma a_1)(\gamma a_2)\dots (\gamma a_m)& ={\gamma }^{\frac{\mathrm{N}𝔭-1}{n}}{a}_1{a}_2\dots a_m\\ & \equiv {\left(\frac{\gamma }{𝔭}\right)}_n{a}_1{a}_2\dots a_m(\mathrm{mod}𝔭),\end{array}$

and on the other hand, since Template:Math is a permutation,

$\begin{array}{ccc}(\gamma a_1)(\gamma a_2)\dots (\gamma a_m)& \equiv {\zeta }_n^{b(1)}{a}_{\pi (1)}{\zeta }_n^{b(2)}{a}_{\pi (2)}\dots {\zeta }_n^{b(m)}{a}_{\pi (m)}& (\mathrm{mod}𝔭)\\ & \equiv {\zeta }_n^{b(1)+b(2)+\dots +b(m)}{a}_{\pi (1)}{a}_{\pi (2)}\dots a_{\pi (m)}& (\mathrm{mod}𝔭)\\ & \equiv {\zeta }_n^{b(1)+b(2)+\dots +b(m)}{a}_1{a}_2\dots a_m& (\mathrm{mod}𝔭),\end{array}$

so

${\left(\frac{\gamma }{𝔭}\right)}_n{a}_1{a}_2\dots a_m\equiv {\zeta }_n^{b(1)+b(2)+\dots +b(m)}{a}_1{a}_2\dots a_m(\mathrm{mod}𝔭),$

and since for all Template:Math, Template:Math and $𝔭$ are coprime, Template:Math can be cancelled from both sides of the congruence,

${\left(\frac{\gamma }{𝔭}\right)}_n\equiv {\zeta }_n^{b(1)+b(2)+\dots +b(m)}(\mathrm{mod}𝔭),$

and the theorem follows from the fact that no two distinct Template:Mathth roots of unity can be congruent (mod $𝔭$).

Relation to the transfer in group theory

Let Template:Math be the multiplicative group of nonzero residue classes in Template:Math, and let Template:Math be the subgroup {+1, −1}. Consider the following coset representatives of Template:Math in Template:Math,

$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

$\varphi :G\to H,$

which turns out to be the map that sends Template:Math to Template:Math, where Template:Math and Template:Math 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