Lemma von Zolotareff

Das Lemma von Zolotareff ist ein mathematischer Satz aus der Zahlentheorie, der eine Verbindung zwischen dem Legendre-Symbol und dem Vorzeichen einer Permutation herstellt. Das Lemma erlaubt einen einfachen Beweis des quadratischen Reziprozitätsgesetzes zur Ermittlung quadratischer Reste. Es ist nach dem russischen Mathematiker Jegor Iwanowitsch Zolotareff benannt, der das Lemma und diesen Beweis 1872 vorlegte. Ferdinand Georg Frobenius verallgemeinerte diese Resultate 1914 für das 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

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 folgt dann die Übereinstimmung mit dem Legendre-Symbol nach 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

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 der Verkettungseigenschaft sowie der Invarianz unter Inversion des Vorzeichens folgt 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 das 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

• 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. 
• Oswald Baumgart: The Quadratic Reciprocity Law: A Collection of Classical Proofs. Birkhäuser, 2015, ISBN 978-3-319-16283-6. 

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

• 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. 
• mathcam: Zolotarev's Lemma. In: PlanetMath. (englisch)