Lemma from Zolotareff

The lemma Zolotareff is a mathematical theorem from the theory of numbers , of a connection between the Legendre symbol and the sign of a permutation is prepared. The lemma allows a simple proof of the quadratic reciprocity law to find quadratic residues . It is named after the Russian mathematician Yegor Ivanovich Zolotareff , who presented the lemma and this proof in 1872. Ferdinand Georg Frobenius generalized these results in 1914 for the Jacobi symbol .

lemma

If there is an integer and an odd prime number that does not divide , then the figure represents ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle a}$

${\displaystyle \pi _{a,p}\colon \mathbb {Z} _{p}^{\times }\to \mathbb {Z} _{p}^{\times },\quad \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}}}$

represents a permutation of the elements of the prime residue class group (the numbers from to ). The lemma of Zolotareff says that the Legendre symbol is equal to the sign of this permutation, that is, ${\displaystyle \mathbb {Z} _{p}^{\times }}$ ${\displaystyle 1}$ ${\displaystyle p-1}$ ${\displaystyle \left({\tfrac {a}{p}}\right)}$

${\displaystyle \left({\frac {a}{p}}\right)=\operatorname {sgn} (\pi _{a,p})}$.

example

Key figures of the permutations π _{a , 7}

${\displaystyle a}$	π a , 7	Cycle type	sign
1	(1, 2, 3, 4, 5, 6)	1 6	1
2	(2, 4, 6, 1, 3, 5)	3 2	1
3	(3, 6, 2, 5, 1, 4)	6 1	−1
4th	(4, 1, 5, 2, 6, 3)	3 2	1
5	(5, 3, 1, 6, 4, 2)	6 1	−1
6th	(6, 5, 4, 3, 2, 1)	2 3	−1

The Legendre symbol is used to study square residues modulo . For a quadratic remainder modulo the corresponding Legendre symbol is the same , for a quadratic non - remainder it is the same . In the following the numbers are the representatives of the prime remainder classes modulo . Then, for example, for because ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle 1,\ldots ,p-1}$ ${\displaystyle p}$ ${\displaystyle p=7}$

${\displaystyle 1^{2}\equiv 1{\pmod {7}}}$

${\displaystyle 2^{2}\equiv 4{\pmod {7}}}$

${\displaystyle 3^{2}\equiv 2{\pmod {7}}}$

the numbers and square residues, while the numbers and square non- residues . The sign of a permutation is equal to the product of the signs of its disjoint cycles , with a cycle of length having the sign . According to Zolotareff's lemma, for example, the permutation now results ${\displaystyle 1,2}$ ${\displaystyle 4}$ ${\displaystyle 3,5}$ ${\displaystyle 6}$ ${\displaystyle l}$ ${\displaystyle (-1)^{l-1}}$ ${\displaystyle a=2}$

${\displaystyle \pi _{2,7}=(2,4,6,1,3,5)=(1~2~4)(3~6~5)}$

with two cycles of length . This applies ${\displaystyle 3}$

${\displaystyle \left({\frac {2}{7}}\right)=\operatorname {sgn} (\pi _{2,7})=(-1)^{2}\cdot (-1)^{2}=1}$

and is a quadratic remainder modulo . For is the associated permutation ${\displaystyle 2}$ ${\displaystyle 7}$ ${\displaystyle a=5}$

${\displaystyle \pi _{5,7}=(5,3,1,6,4,2)=(1~5~4~6~2~3)}$

a cycle of length . This applies ${\displaystyle 6}$

${\displaystyle \left({\frac {5}{7}}\right)=\operatorname {sgn} (\pi _{5,7})=(-1)^{5}=-1}$

and is a quadratic non-remainder modulo . ${\displaystyle 5}$ ${\displaystyle 7}$

proof

Denotes the order of in the prime residue class group , then the permutation breaks down into cycles of length . This results in the sign of ${\displaystyle l}$ ${\displaystyle a}$ ${\displaystyle \mathbb {Z} _{p}^{\times }}$ ${\displaystyle \pi _{a,p}}$ ${\displaystyle (p-1)/l}$ ${\displaystyle l}$ ${\displaystyle \pi _{a,p}}$

${\displaystyle \operatorname {sgn} (\pi _{a,p})=(-1)^{(l-1)(p-1)/l}}$.

Is now straight, then results ${\displaystyle l}$

${\displaystyle \operatorname {sgn} (\pi _{a,p})=(-1)^{(p-1)/l}\equiv (a^{l/2})^{(p-1)/l}{\pmod {p}}\equiv a^{(p-1)/2}{\pmod {p}}}$.

If odd, then is a factor of and it results ${\displaystyle l}$ ${\displaystyle 2l}$ ${\displaystyle p-1}$

${\displaystyle \operatorname {sgn} (\pi _{a,p})=1\equiv (a^{l})^{(p-1)/2l}{\pmod {p}}\equiv a^{(p-1)/2}{\pmod {p}}}$.

In both cases the agreement with the Legendre symbol follows according to Euler's criterion

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}{\pmod {p}}}$.

annotation

The figure shows a surjective homomorphism from the prime residue class group into the group . The surjectivity follows from the fact that for a primitive root modulo the permutation represents a -cycle with a sign . The core of this figure is therefore a subgroup of with index . However, since is cyclic , the only subgroup of this kind is the multiplicative group of quadratic residues. This also means that it corresponds to the Legendre symbol. ${\displaystyle a\mapsto \operatorname {sgn} (\pi _{a,p})}$ ${\displaystyle \mathbb {Z} _{p}^{\times }}$ ${\displaystyle (\{1,-1\},\cdot )}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle \pi _{a,p}}$ ${\displaystyle (p-1)}$ ${\displaystyle -1}$ ${\displaystyle \mathbb {Z} _{p}^{\times }}$ ${\displaystyle 2}$ ${\displaystyle \mathbb {Z} _{p}^{\times }}$

use

Quadratic law of reciprocity

Permutation τ _5.7 in matrix form

	0	1	2	3	4th	5	6th
0	0	5	10	15th	20th	25th	30th
1	1	6th	11	16	21st	26th	31
2	2	7th	12	17th	22nd	27	32
3	3	8th	13	18th	23	28	33
4th	4th	9	14th	19th	24	29	34

Permutation α _5.7 in matrix form

	0	1	2	3	4th	5	6th
0	0	15th	30th	10	25th	5	20th
1	21st	1	16	31	11	26th	6th
2	7th	22nd	2	17th	32	12	27
3	28	8th	23	3	18th	33	13
4th	14th	29	9	24	4th	19th	34

α _5.7 after column dislocations

	0	1	2	3	4th	5	6th
0	0	1	2	3	4th	5	6th
1	21st	22nd	23	24	25th	26th	27
2	7th	8th	9	10	11	12	13
3	28	29	30th	31	32	33	34
4th	14th	15th	16	17th	18th	19th	20th

Zolotareff used the lemma to prove the quadratic reciprocity law . Let this be and two different odd prime numbers . According to the Chinese remainder of the law , every number can be clearly represented in the form with and . Now let's look at the two permutations ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle z\in \mathbb {Z} _{pq}}$ ${\displaystyle z=qi+j}$ ${\displaystyle i\in \mathbb {Z} _{p}}$ ${\displaystyle j\in \mathbb {Z} _{q}}$ ${\displaystyle \mathbb {Z} _{pq}}$

${\displaystyle \tau _{p,q}(qi+j)\equiv i+pj{\pmod {pq}}}$

and

${\displaystyle \alpha _{p,q}(qi+j)\equiv q^{-1}qi+p^{-1}pj{\pmod {pq}}}$

considered, wherein the inverse element to in and the inverse element to in call. If the values ​​of these permutations are arranged in a rectangular matrix consisting of rows and columns, then a column-by-column and a diagonal listing of the numbers from to (a row-by-row listing would correspond to the identical permutation ). The permutation is the transposition permutation that swaps rows and columns of a matrix. The sign of is ${\displaystyle p^{-1}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle q^{-1}}$ ${\displaystyle q}$ ${\displaystyle \mathbb {Z} _{p}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \tau _{p,q}}$ ${\displaystyle \alpha _{p,q}}$ ${\displaystyle 0}$ ${\displaystyle pq-1}$ ${\displaystyle \tau _{p,q}}$ ${\displaystyle (q\times p)}$ ${\displaystyle \tau _{p,q}}$

${\displaystyle \operatorname {sgn} (\tau _{p,q})=(-1)^{{\tbinom {p}{2}}{\tbinom {q}{2}}}=(-1)^{{\tfrac {p-1}{2}}{\tfrac {q-1}{2}}}=\operatorname {sgn} (\tau _{q,p})}$,

since every pair of two-element subsets and produces exactly one deficit . In the columns of the permutation , the values ​​of the permutation (with an additional fixed point) are cyclically offset, multiplied by and increased by the column index . The cyclic offsets can be reversed with the help of column-wise cyclic permutations without changing the sign of , since cyclic permutations of odd length are always even . This creates the identical permutation, in which the lines are swapped according to the permutation . The following therefore applies to the sign of ${\displaystyle \{i,i'\}\subseteq \mathbb {Z} _{p}}$ ${\displaystyle \{j,j'\}\subseteq \mathbb {Z} _{q}}$ ${\displaystyle \alpha _{p,q}}$ ${\displaystyle \pi _{q,p}^{-1}}$ ${\displaystyle 0}$ ${\displaystyle q}$ ${\displaystyle j}$ ${\displaystyle \alpha _{p,q}}$ ${\displaystyle \pi _{q,p}^{-1}}$ ${\displaystyle \alpha _{p,q}}$

${\displaystyle \operatorname {sgn} (\alpha _{p,q})=\operatorname {sgn} (\pi _{q,p}^{-1})^{q}=\operatorname {sgn} (\pi _{q,p})=\left({\frac {q}{p}}\right)}$.

In the lines of the permutation , the values ​​of the permutation (with as an additional fixed point) are accordingly cyclically offset, multiplied by and increased by the column index . If the permutation is transposed with the help of the permutation , then the sign of the transposed permutation results analogously to ${\displaystyle \alpha _{p,q}}$ ${\displaystyle \pi _{p,q}^{-1}}$ ${\displaystyle 0}$ ${\displaystyle p}$ ${\displaystyle i}$ ${\displaystyle \alpha _{p,q}}$ ${\displaystyle \tau _{q,p}}$

${\displaystyle \operatorname {sgn} (\alpha _{p,q}\circ \tau _{q,p})=\left({\frac {p}{q}}\right)}$.

With the chaining property and the invariance under inversion of the sign it follows from

${\displaystyle \operatorname {sgn} (\alpha _{p,q})=\operatorname {sgn} (\alpha _{p,q}\circ \tau _{q,p}\circ \tau _{q,p}^{-1})=\operatorname {sgn} (\alpha _{p,q}\circ \tau _{q,p})\cdot \operatorname {sgn} (\tau _{q,p})}$

then the quadratic reciprocity law

${\displaystyle \left({\frac {q}{p}}\right)=\left({\frac {p}{q}}\right)\cdot (-1)^{{\tfrac {p-1}{2}}{\tfrac {q-1}{2}}}}$.

Jacobi symbol

With the help of Zolotareff's lemma, the Legendre symbol can be generalized to the Jacobi symbol , for which the same notation is usually used. If this is an odd number and any whole number that is relatively prime , then the Jacobi symbol can go through ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$

${\displaystyle \left({\frac {a}{n}}\right)=\operatorname {sgn} (\pi _{a,n})}$

To be defined. In the event that is odd, the quadratic reciprocity law also applies to the Jacobi symbol. ${\displaystyle a}$

literature

• Oswald Baumgart: The Quadratic Reciprocity Law: A Collection of Classical Proofs . Birkhäuser, 2015, ISBN 978-3-319-16283-6 .
• Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Discrete algebraic methods . de Gruyter, 2013, ISBN 978-3-11-031261-4 .
• Franz Lemmermeyer: Reciprocity Laws. From Euler to Eisenstein . Springer, 2000, ISBN 3-540-66957-4 .

Original work

• Jegor Ivanovich Zolotareff: Nouvelle demonstration de la loi de réciprocité de Legendre . In: Nouvelles Annales de Mathématiques 2e série . tape 11 , 1872, p. 354-362 ( online [PDF]).
• Ferdinand Georg Frobenius: About the quadratic reciprocity law . In: Session reports of the Royal Prussian Academy of Sciences in Berlin . 1914, p. 335-349 ( online [PDF]).

Individual evidence

1. ↑ Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Discrete algebraic methods . de Gruyter, 2013, p. 42 .
2. ↑ Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Discrete algebraic methods . de Gruyter, 2013, p. 43 .

Web links

• mathcam: Zolotarev's lemma . In: PlanetMath . (English)
• Matt Baker: Quadratic reciprocity and Zolotarev's Lemma. July 3, 2013, accessed July 31, 2015 . 
• Urs Schreiber: Quadratic reciprocity law. nlab, September 1, 2014, accessed July 31, 2015 .