Lemma von Zolotareff

mathematischer Satz

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.

Ist   eine ganze Zahl und   eine ungerade Primzahl, die   nicht teilt, dann stellt die Abbildung

 

eine Permutation der Elemente der primen Restklassengruppe   (der Zahlen von   bis  ) dar. Das Lemma von Zolotareff besagt nun, dass das Legendre-Symbol   gleich dem Vorzeichen dieser Permutation ist, das heißt,[1]

 .

Beispiel

Bearbeiten
Kennzahlen der Permutationen πa,7
  πa,7 Zykeltyp Vorzeichen
1 (1, 2, 3, 4, 5, 6) 16 1
2 (2, 4, 6, 1, 3, 5) 32 1
3 (3, 6, 2, 5, 1, 4) 61 −1
4 (4, 1, 5, 2, 6, 3) 32 1
5 (5, 3, 1, 6, 4, 2) 61 −1
6 (6, 5, 4, 3, 2, 1) 23 −1

Das Legendre-Symbol dient zur Untersuchung quadratischer Reste modulo  . Für einen quadratischen Rest   modulo   ist das zugehörige Legendre-Symbol gleich  , für einen quadratischen Nichtrest ist es gleich  . Im Folgenden seien die Zahlen   die Repräsentanten der primen Restklassen modulo  . Dann sind beispielsweise für   wegen

 
 
 

die Zahlen   und   quadratische Reste, während die Zahlen   und   quadratische Nichtreste sind. Das Vorzeichen einer Permutation ist gleich dem Produkt der Vorzeichen ihrer disjunkten Zyklen, wobei ein Zyklus der Länge   das Vorzeichen   besitzt. Nach dem Lemma von Zolotareff ergibt sich nun beispielsweise für   die Permutation

 

mit zwei Zyklen der Länge  . Damit gilt

 

und   ist ein quadratischer Rest modulo  . Für   ist die zugehörige Permutation

 

ein Zyklus der Länge  . Damit gilt

 

und   ist ein quadratischer Nichtrest modulo  .

Bezeichnet   die Ordnung von   in der primen Restklassengruppe  , dann zerfällt die Permutation   in   Zyklen der Länge  . Daraus ergibt sich für das Vorzeichen von  

 .

Ist nun   gerade, dann ergibt sich

 .

Ist   ungerade, dann ist   ein Teiler von   und es ergibt sich

 .

In beiden Fällen folgt dann die Übereinstimmung mit dem Legendre-Symbol nach dem eulerschen Kriterium

 .

Anmerkung

Die Abbildung   stellt einen surjektiven Homomorphismus von der primen Restklassengruppe   in die Gruppe   dar. Die Surjektivität folgt daraus, dass für eine Primitivwurzel   modulo   die Permutation   einen  -Zyklus mit Vorzeichen   darstellt. Der Kern dieser Abbildung ist daher eine Untergruppe von   mit Index  . Nachdem aber   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

Bearbeiten

Quadratisches Reziprozitätsgesetz

Bearbeiten
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   und   zwei verschiedene ungerade Primzahlen. Nach dem chinesischen Restsatz lässt sich jede Zahl   eindeutig in der Form   mit   und   darstellen. Nun werden auf   die beiden Permutationen

 

und

 

betrachtet, wobei   das inverse Element zu   in   und   das inverse Element zu   in   bezeichnen. Werden die Werte dieser Permutationen jeweils in einer rechteckigen Matrix, bestehend aus   Zeilen und   Spalten, angeordnet, dann entspricht   einer spaltenweisen und   einer diagonalen Aufzählung der Zahlen von   bis   (eine zeilenweise Aufzählung würde gerade der identischen Permutation entsprechen). Die Permutation   ist die Transpositionspermutation, die Zeilen und Spalten einer  -Matrix vertauscht. Das Vorzeichen von   ist

 ,

da jedes Paar zweielementiger Teilmengen   und   genau einen Fehlstand erzeugt. In den Spalten der Permutation   finden sich zyklisch versetzt die Werte der Permutation   (mit   als zusätzlichem Fixpunkt) mit   multipliziert und jeweils um den Spaltenindex   erhöht. Die zyklischen Versetzungen können mit Hilfe spaltenweiser zyklischer Permutationen rückgängig gemacht werden, ohne dass sich das Vorzeichen von   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   vertauscht sind. Für das Vorzeichen von   gilt daher

 .

In den Zeilen der Permutation   finden sich entsprechend zyklisch versetzt die Werte der Permutation   (mit   als zusätzlichem Fixpunkt) mit   multipliziert und um den Spaltenindex   erhöht. Wird die Permutation   mit Hilfe der Permutation   transponiert, dann ergibt sich analog zu vorher das Vorzeichen der transponierten Permutation zu

 .

Mit der Verkettungseigenschaft sowie der Invarianz unter Inversion des Vorzeichens folgt aus

 

dann das quadratische Reziprozitätsgesetz

 .

Jacobi-Symbol

Bearbeiten

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   eine ungerade Zahl und   eine beliebige ganze Zahl, die teilerfremd zu   ist, dann kann das Jacobi-Symbol durch

 

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

Literatur

Bearbeiten

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

Bearbeiten
  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.
Bearbeiten