Lemma von Zolotareff

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

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

Quadratisches Reziprozitätsgesetz

[Bearbeiten | Quelltext 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

.

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]

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