Lemma von Zolotareff

Das Lemma v​on Zolotareff i​st ein mathematischer Satz a​us der Zahlentheorie, d​er eine Verbindung zwischen d​em Legendre-Symbol u​nd dem Vorzeichen e​iner Permutation herstellt. Das Lemma erlaubt e​inen einfachen Beweis d​es quadratischen Reziprozitätsgesetzes z​ur Ermittlung quadratischer Reste. Es i​st nach d​em russischen Mathematiker Jegor Iwanowitsch Zolotareff benannt, d​er das Lemma u​nd diesen Beweis 1872 vorlegte. Ferdinand Georg Frobenius verallgemeinerte d​iese Resultate 1914 für d​as Jacobi-Symbol.

Lemma

Ist ${\displaystyle a}$ eine ganze Zahl und ${\displaystyle p}$ eine ungerade Primzahl, die ${\displaystyle a}$ nicht teilt, dann stellt die Abbildung

${\displaystyle \pi _{a,p}:~\mathbb {Z} _{p}^{\times }\to \mathbb {Z} _{p}^{\times },\quad \pi _{a,p}({\bar {k}}):=a\,{\bar {k}}={\overline {a\,k}}=\{a\,k+m\,p;~m\in \mathbb {Z} \}}$

eine Permutation der Elemente der primen Restklassengruppe ${\displaystyle \mathbb {Z} _{p}^{\times }}$ (der Zahlen von ${\displaystyle 1}$ bis ${\displaystyle p-1}$) dar. Das Lemma von Zolotareff besagt nun, dass das Legendre-Symbol ${\displaystyle \left({\tfrac {a}{p}}\right)}$ gleich dem Vorzeichen dieser Permutation ist, das heißt,[1]

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

Beispiel

Kennzahlen der Permutationen π_a,7

${\displaystyle a}$	πa,7	Zykeltyp	Vorzeichen
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
4	(4, 1, 5, 2, 6, 3)	3^2	1
5	(5, 3, 1, 6, 4, 2)	6^1	−1
6	(6, 5, 4, 3, 2, 1)	2^3	−1

Das Legendre-Symbol dient zur Untersuchung quadratischer Reste modulo ${\displaystyle p}$. Für einen quadratischen Rest ${\displaystyle a}$ modulo ${\displaystyle p}$ ist das zugehörige Legendre-Symbol gleich ${\displaystyle 1}$, für einen quadratischen Nichtrest ist es gleich ${\displaystyle -1}$. Im Folgenden seien die Zahlen ${\displaystyle 1,\ldots ,p-1}$ die Repräsentanten der primen Restklassen modulo ${\displaystyle p}$. Dann sind beispielsweise für ${\displaystyle p=7}$ wegen

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

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

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

die Zahlen ${\displaystyle 1,2}$ und ${\displaystyle 4}$ quadratische Reste, während die Zahlen ${\displaystyle 3,5}$ und ${\displaystyle 6}$ quadratische Nichtreste sind. Das Vorzeichen einer Permutation ist gleich dem Produkt der Vorzeichen ihrer disjunkten Zyklen, wobei ein Zyklus der Länge ${\displaystyle l}$ das Vorzeichen ${\displaystyle (-1)^{l-1}}$ besitzt. Nach dem Lemma von Zolotareff ergibt sich nun beispielsweise für ${\displaystyle a=2}$ die Permutation

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

mit zwei Zyklen der Länge ${\displaystyle 3}$. Damit gilt

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

und ${\displaystyle 2}$ ist ein quadratischer Rest modulo ${\displaystyle 7}$. Für ${\displaystyle a=5}$ ist die zugehörige Permutation

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

ein Zyklus der Länge ${\displaystyle 6}$. Damit gilt

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

und ${\displaystyle 5}$ ist ein quadratischer Nichtrest modulo ${\displaystyle 7}$.

Beweis

Bezeichnet ${\displaystyle l}$ die Ordnung von ${\displaystyle a}$ in der primen Restklassengruppe ${\displaystyle \mathbb {Z} _{p}^{\times }}$, dann zerfällt die Permutation ${\displaystyle \pi _{a,p}}$ in ${\displaystyle (p-1)/l}$ Zyklen der Länge ${\displaystyle l}$. Daraus ergibt sich für das Vorzeichen von ${\displaystyle \pi _{a,p}}$

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

Ist nun ${\displaystyle l}$ gerade, dann ergibt sich

${\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}}}$.

Ist ${\displaystyle l}$ ungerade, dann ist ${\displaystyle 2l}$ ein Teiler von ${\displaystyle p-1}$ und es ergibt sich

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

In beiden Fällen f​olgt dann d​ie Übereinstimmung m​it dem Legendre-Symbol n​ach dem eulerschen Kriterium

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

Anmerkung

Die Abbildung ${\displaystyle a\mapsto \operatorname {sgn} (\pi _{a,p})}$ stellt einen surjektiven Homomorphismus von der primen Restklassengruppe ${\displaystyle \mathbb {Z} _{p}^{\times }}$ in die Gruppe ${\displaystyle (\{1,-1\},\cdot )}$ dar. Die Surjektivität folgt daraus, dass für eine Primitivwurzel ${\displaystyle a}$ modulo ${\displaystyle p}$ die Permutation ${\displaystyle \pi _{a,p}}$ einen ${\displaystyle (p-1)}$-Zyklus mit Vorzeichen ${\displaystyle -1}$ darstellt. Der Kern dieser Abbildung ist daher eine Untergruppe von ${\displaystyle \mathbb {Z} _{p}^{\times }}$ mit Index ${\displaystyle 2}$. Nachdem aber ${\displaystyle \mathbb {Z} _{p}^{\times }}$ zyklisch ist, ist die einzige Untergruppe dieser Art die multiplikative Gruppe der quadratischen Reste. Daraus folgt dann ebenfalls die Übereinstimmung mit dem Legendre-Symbol.

Verwendung

Quadratisches Reziprozitätsgesetz

Permutation τ_5,7 in Matrixform

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

Permutation α_5,7 in Matrixform

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

α_5,7 nach Spaltenversetzungen

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

Zolotareff verwendete das Lemma, um das quadratische Reziprozitätsgesetz zu beweisen. Seien hierzu ${\displaystyle p}$ und ${\displaystyle q}$ zwei verschiedene ungerade Primzahlen. Nach dem chinesischen Restsatz lässt sich jede Zahl ${\displaystyle z\in \mathbb {Z} _{pq}}$ eindeutig in der Form ${\displaystyle z=qi+j}$ mit ${\displaystyle i\in \mathbb {Z} _{p}}$ und ${\displaystyle j\in \mathbb {Z} _{q}}$ darstellen. Nun werden auf ${\displaystyle \mathbb {Z} _{pq}}$ die beiden Permutationen

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

und

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

betrachtet, wobei ${\displaystyle p^{-1}}$ das inverse Element zu ${\displaystyle p}$ in ${\displaystyle \mathbb {Z} _{q}}$ und ${\displaystyle q^{-1}}$ das inverse Element zu ${\displaystyle q}$ in ${\displaystyle \mathbb {Z} _{p}}$ bezeichnen. Werden die Werte dieser Permutationen jeweils in einer rechteckigen Matrix, bestehend aus ${\displaystyle p}$ Zeilen und ${\displaystyle q}$ Spalten, angeordnet, dann entspricht ${\displaystyle \tau _{p,q}}$ einer spaltenweisen und ${\displaystyle \alpha _{p,q}}$ einer diagonalen Aufzählung der Zahlen von ${\displaystyle 0}$ bis ${\displaystyle pq-1}$ (eine zeilenweise Aufzählung würde gerade der identischen Permutation entsprechen). Die Permutation ${\displaystyle \tau _{p,q}}$ ist die Transpositionspermutation, die Zeilen und Spalten einer ${\displaystyle (q\times p)}$-Matrix vertauscht. Das Vorzeichen von ${\displaystyle \tau _{p,q}}$ ist

${\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})}$,

da jedes Paar zweielementiger Teilmengen ${\displaystyle \{i,i'\}\subseteq \mathbb {Z} _{p}}$ und ${\displaystyle \{j,j'\}\subseteq \mathbb {Z} _{q}}$ genau einen Fehlstand erzeugt. In den Spalten der Permutation ${\displaystyle \alpha _{p,q}}$ finden sich zyklisch versetzt die Werte der Permutation ${\displaystyle \pi _{q,p}^{-1}}$ (mit ${\displaystyle 0}$ als zusätzlichem Fixpunkt) mit ${\displaystyle q}$ multipliziert und jeweils um den Spaltenindex ${\displaystyle j}$ erhöht. Die zyklischen Versetzungen können mit Hilfe spaltenweiser zyklischer Permutationen rückgängig gemacht werden, ohne dass sich das Vorzeichen von ${\displaystyle \alpha _{p,q}}$ verändert, da zyklische Permutationen ungerader Länge stets gerade sind. Auf diese Weise entsteht die identische Permutation, bei der die Zeilen gemäß der Permutation ${\displaystyle \pi _{q,p}^{-1}}$ vertauscht sind. Für das Vorzeichen von ${\displaystyle \alpha _{p,q}}$ gilt daher

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

In den Zeilen der Permutation ${\displaystyle \alpha _{p,q}}$ finden sich entsprechend zyklisch versetzt die Werte der Permutation ${\displaystyle \pi _{p,q}^{-1}}$ (mit ${\displaystyle 0}$ als zusätzlichem Fixpunkt) mit ${\displaystyle p}$ multipliziert und um den Spaltenindex ${\displaystyle i}$ erhöht. Wird die Permutation ${\displaystyle \alpha _{p,q}}$ mit Hilfe der Permutation ${\displaystyle \tau _{q,p}}$ transponiert, dann ergibt sich analog zu vorher das Vorzeichen der transponierten Permutation zu

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

Mit d​er Verkettungseigenschaft s​owie der Invarianz u​nter Inversion d​es Vorzeichens f​olgt aus

${\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})}$

dann d​as quadratische Reziprozitätsgesetz

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

Jacobi-Symbol

Mit Hilfe des Lemmas von Zolotareff lässt sich das Legendre-Symbol zum Jacobi-Symbol verallgemeinern, für das auch üblicherweise die gleiche Notation verwendet wird. Ist hierzu ${\displaystyle n}$ eine ungerade Zahl und ${\displaystyle a}$ eine beliebige ganze Zahl, die teilerfremd zu ${\displaystyle n}$ ist, dann kann das Jacobi-Symbol durch

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

definiert werden. Im Fall, dass ${\displaystyle a}$ ungerade ist, gilt für das Jacobi-Symbol ebenfalls das quadratische Reziprozitätsgesetz.[2]

Literatur

• 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: Diskrete algebraische Methoden. de Gruyter, 2013, ISBN 978-3-11-031261-4.
• Franz Lemmermeyer: Reciprocity Laws. From Euler to Eisenstein. Springer, 2000, ISBN 3-540-66957-4.

Originalarbeiten

• Jegor Iwanowitsch Zolotareff: Nouvelle démonstration de la loi de réciprocité de Legendre. In: Nouvelles Annales de Mathématiques 2e série. Band 11, 1872, S. 354–362 (Online [PDF]).
• Ferdinand Georg Frobenius: Über das quadratische Reziprozitätsgesetz. In: Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin. 1914, S. 335–349 (Online [PDF]).

Einzelnachweise

1. Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden. de Gruyter, 2013, S. 42.
2. Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden. de Gruyter, 2013, S. 43.

Weblinks

• mathcam: Zolotarev's Lemma. In: PlanetMath. (englisch)
• Matt Baker: Quadratic reciprocity and Zolotarev’s Lemma. 3. Juli 2013, abgerufen am 31. Juli 2015.
• Urs Schreiber: Quadratic reciprocity law. nlab, 1. September 2014, abgerufen am 31. Juli 2015.