www.wikidata.de-de.nina.az

Lemma von Zolotareff Das ist ein mathematischer Satz aus der Zahlentheorie der eine Verbindung zwischen dem Legendre Sym

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 Bearbeiten

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,

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 .

Beweis Bearbeiten

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.

Literatur Bearbeiten

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Reziprozitatsgesetzes 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 fur das Jacobi Symbol Inhaltsverzeichnis 1 Lemma 2 Beispiel 3 Beweis 4 Verwendung 4 1 Quadratisches Reziprozitatsgesetz 4 2 Jacobi Symbol 5 Literatur 6 Einzelnachweise 7 WeblinksLemma BearbeitenIst a displaystyle a nbsp eine ganze Zahl und p displaystyle p nbsp eine ungerade Primzahl die a displaystyle a nbsp nicht teilt dann stellt die Abbildung p a p Z p Z p p a p k a k a k a k m p m Z 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 nbsp eine Permutation der Elemente der primen Restklassengruppe Z p displaystyle mathbb Z p times nbsp der Zahlen von 1 displaystyle 1 nbsp bis p 1 displaystyle p 1 nbsp dar Das Lemma von Zolotareff besagt nun dass das Legendre Symbol a p displaystyle left tfrac a p right nbsp gleich dem Vorzeichen dieser Permutation ist das heisst 1 a p sgn p a p displaystyle left frac a p right operatorname sgn pi a p nbsp Beispiel BearbeitenKennzahlen der Permutationen pa 7 a displaystyle a nbsp pa 7 Zykeltyp Vorzeichen1 1 2 3 4 5 6 16 12 2 4 6 1 3 5 32 13 3 6 2 5 1 4 61 14 4 1 5 2 6 3 32 15 5 3 1 6 4 2 61 16 6 5 4 3 2 1 23 1Das Legendre Symbol dient zur Untersuchung quadratischer Reste modulo p displaystyle p nbsp Fur einen quadratischen Rest a displaystyle a nbsp modulo p displaystyle p nbsp ist das zugehorige Legendre Symbol gleich 1 displaystyle 1 nbsp fur einen quadratischen Nichtrest ist es gleich 1 displaystyle 1 nbsp Im Folgenden seien die Zahlen 1 p 1 displaystyle 1 ldots p 1 nbsp die Reprasentanten der primen Restklassen modulo p displaystyle p nbsp Dann sind beispielsweise fur p 7 displaystyle p 7 nbsp wegen 1 2 1 mod 7 displaystyle 1 2 equiv 1 pmod 7 nbsp 2 2 4 mod 7 displaystyle 2 2 equiv 4 pmod 7 nbsp 3 2 2 mod 7 displaystyle 3 2 equiv 2 pmod 7 nbsp die Zahlen 1 2 displaystyle 1 2 nbsp und 4 displaystyle 4 nbsp quadratische Reste wahrend die Zahlen 3 5 displaystyle 3 5 nbsp und 6 displaystyle 6 nbsp quadratische Nichtreste sind Das Vorzeichen einer Permutation ist gleich dem Produkt der Vorzeichen ihrer disjunkten Zyklen wobei ein Zyklus der Lange l displaystyle l nbsp das Vorzeichen 1 l 1 displaystyle 1 l 1 nbsp besitzt Nach dem Lemma von Zolotareff ergibt sich nun beispielsweise fur a 2 displaystyle a 2 nbsp die Permutation p 2 7 2 4 6 1 3 5 1 2 4 3 6 5 displaystyle pi 2 7 2 4 6 1 3 5 1 2 4 3 6 5 nbsp mit zwei Zyklen der Lange 3 displaystyle 3 nbsp Damit gilt 2 7 sgn p 2 7 1 2 1 2 1 displaystyle left frac 2 7 right operatorname sgn pi 2 7 1 2 cdot 1 2 1 nbsp und 2 displaystyle 2 nbsp ist ein quadratischer Rest modulo 7 displaystyle 7 nbsp Fur a 5 displaystyle a 5 nbsp ist die zugehorige Permutation p 5 7 5 3 1 6 4 2 1 5 4 6 2 3 displaystyle pi 5 7 5 3 1 6 4 2 1 5 4 6 2 3 nbsp ein Zyklus der Lange 6 displaystyle 6 nbsp Damit gilt 5 7 sgn p 5 7 1 5 1 displaystyle left frac 5 7 right operatorname sgn pi 5 7 1 5 1 nbsp und 5 displaystyle 5 nbsp ist ein quadratischer Nichtrest modulo 7 displaystyle 7 nbsp Beweis BearbeitenBezeichnet l displaystyle l nbsp die Ordnung von a displaystyle a nbsp in der primen Restklassengruppe Z p displaystyle mathbb Z p times nbsp dann zerfallt die Permutation p a p displaystyle pi a p nbsp in p 1 l displaystyle p 1 l nbsp Zyklen der Lange l displaystyle l nbsp Daraus ergibt sich fur das Vorzeichen von p a p displaystyle pi a p nbsp sgn p a p 1 l 1 p 1 l displaystyle operatorname sgn pi a p 1 l 1 p 1 l nbsp Ist nun l displaystyle l nbsp gerade dann ergibt sich sgn p a p 1 p 1 l a l 2 p 1 l mod p a p 1 2 mod p 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 nbsp Ist l displaystyle l nbsp ungerade dann ist 2 l displaystyle 2l nbsp ein Teiler von p 1 displaystyle p 1 nbsp und es ergibt sich sgn p a p 1 a l p 1 2 l mod p a p 1 2 mod p displaystyle operatorname sgn pi a p 1 equiv a l p 1 2l pmod p equiv a p 1 2 pmod p nbsp In beiden Fallen folgt dann die Ubereinstimmung mit dem Legendre Symbol nach dem eulerschen Kriterium a p a p 1 2 mod p displaystyle left frac a p right equiv a p 1 2 pmod p nbsp AnmerkungDie Abbildung a sgn p a p displaystyle a mapsto operatorname sgn pi a p nbsp stellt einen surjektiven Homomorphismus von der primen Restklassengruppe Z p displaystyle mathbb Z p times nbsp in die Gruppe 1 1 displaystyle 1 1 cdot nbsp dar Die Surjektivitat folgt daraus dass fur eine Primitivwurzel a displaystyle a nbsp modulo p displaystyle p nbsp die Permutation p a p displaystyle pi a p nbsp einen p 1 displaystyle p 1 nbsp Zyklus mit Vorzeichen 1 displaystyle 1 nbsp darstellt Der Kern dieser Abbildung ist daher eine Untergruppe von Z p displaystyle mathbb Z p times nbsp mit Index 2 displaystyle 2 nbsp Nachdem aber Z p displaystyle mathbb Z p times nbsp zyklisch ist ist die einzige Untergruppe dieser Art die multiplikative Gruppe der quadratischen Reste Daraus folgt dann ebenfalls die Ubereinstimmung mit dem Legendre Symbol Verwendung BearbeitenQuadratisches Reziprozitatsgesetz Bearbeiten Permutation t5 7 in Matrixform 0 1 2 3 4 5 60 0 5 10 15 20 25 301 1 6 11 16 21 26 312 2 7 12 17 22 27 323 3 8 13 18 23 28 334 4 9 14 19 24 29 34Permutation a5 7 in Matrixform 0 1 2 3 4 5 60 0 15 30 10 25 5 201 21 1 16 31 11 26 62 7 22 2 17 32 12 273 28 8 23 3 18 33 134 14 29 9 24 4 19 34a5 7 nach Spaltenversetzungen 0 1 2 3 4 5 60 0 1 2 3 4 5 61 21 22 23 24 25 26 272 7 8 9 10 11 12 133 28 29 30 31 32 33 344 14 15 16 17 18 19 20Zolotareff verwendete das Lemma um das quadratische Reziprozitatsgesetz zu beweisen Seien hierzu p displaystyle p nbsp und q displaystyle q nbsp zwei verschiedene ungerade Primzahlen Nach dem chinesischen Restsatz lasst sich jede Zahl z Z p q displaystyle z in mathbb Z pq nbsp eindeutig in der Form z q i j displaystyle z qi j nbsp mit i Z p displaystyle i in mathbb Z p nbsp und j Z q displaystyle j in mathbb Z q nbsp darstellen Nun werden auf Z p q displaystyle mathbb Z pq nbsp die beiden Permutationen t p q q i j i p j mod p q displaystyle tau p q qi j equiv i pj pmod pq nbsp und a p q q i j q 1 q i p 1 p j mod p q displaystyle alpha p q qi j equiv q 1 qi p 1 pj pmod pq nbsp betrachtet wobei p 1 displaystyle p 1 nbsp das inverse Element zu p displaystyle p nbsp in Z q displaystyle mathbb Z q nbsp und q 1 displaystyle q 1 nbsp das inverse Element zu q displaystyle q nbsp in Z p displaystyle mathbb Z p nbsp bezeichnen Werden die Werte dieser Permutationen jeweils in einer rechteckigen Matrix bestehend aus p displaystyle p nbsp Zeilen und q displaystyle q nbsp Spalten angeordnet dann entspricht t p q displaystyle tau p q nbsp einer spaltenweisen und a p q displaystyle alpha p q nbsp einer diagonalen Aufzahlung der Zahlen von 0 displaystyle 0 nbsp bis p q 1 displaystyle pq 1 nbsp eine zeilenweise Aufzahlung wurde gerade der identischen Permutation entsprechen Die Permutation t p q displaystyle tau p q nbsp ist die Transpositionspermutation die Zeilen und Spalten einer q p displaystyle q times p nbsp Matrix vertauscht Das Vorzeichen von t p q displaystyle tau p q nbsp ist sgn t p q 1 p 2 q 2 1 p 1 2 q 1 2 sgn t q p 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 nbsp da jedes Paar zweielementiger Teilmengen i i Z p displaystyle i i subseteq mathbb Z p nbsp und j j Z q displaystyle j j subseteq mathbb Z q nbsp genau einen Fehlstand erzeugt In den Spalten der Permutation a p q displaystyle alpha p q nbsp finden sich zyklisch versetzt die Werte der Permutation p q p 1 displaystyle pi q p 1 nbsp mit 0 displaystyle 0 nbsp als zusatzlichem Fixpunkt mit q displaystyle q nbsp multipliziert und jeweils um den Spaltenindex j displaystyle j nbsp erhoht Die zyklischen Versetzungen konnen mit Hilfe spaltenweiser zyklischer Permutationen ruckgangig gemacht werden ohne dass sich das Vorzeichen von a p q displaystyle alpha p q nbsp verandert da zyklische Permutationen ungerader Lange stets gerade sind Auf diese Weise entsteht die identische Permutation bei der die Zeilen gemass der Permutation p q p 1 displaystyle pi q p 1 nbsp vertauscht sind Fur das Vorzeichen von a p q displaystyle alpha p q nbsp gilt daher sgn a p q sgn p q p 1 q sgn p q p q p displaystyle operatorname sgn alpha p q operatorname sgn pi q p 1 q operatorname sgn pi q p left frac q p right nbsp In den Zeilen der Permutation a p q displaystyle alpha p q nbsp finden sich entsprechend zyklisch versetzt die Werte der Permutation p p q 1 displaystyle pi p q 1 nbsp mit 0 displaystyle 0 nbsp als zusatzlichem Fixpunkt mit p displaystyle p nbsp multipliziert und um den Spaltenindex i displaystyle i nbsp erhoht Wird die Permutation a p q displaystyle alpha p q nbsp mit Hilfe der Permutation t q p displaystyle tau q p nbsp transponiert dann ergibt sich analog zu vorher das Vorzeichen der transponierten Permutation zu sgn a p q t q p p q displaystyle operatorname sgn alpha p q circ tau q p left frac p q right nbsp Mit der Verkettungseigenschaft sowie der Invarianz unter Inversion des Vorzeichens folgt aus sgn a p q sgn a p q t q p t q p 1 sgn a p q t q p sgn t q p 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 nbsp dann das quadratische Reziprozitatsgesetz q p p q 1 p 1 2 q 1 2 displaystyle left frac q p right left frac p q right cdot 1 tfrac p 1 2 tfrac q 1 2 nbsp Jacobi Symbol Bearbeiten Mit Hilfe des Lemmas von Zolotareff lasst sich das Legendre Symbol zum Jacobi Symbol verallgemeinern fur das auch ublicherweise die gleiche Notation verwendet wird Ist hierzu n displaystyle n nbsp eine ungerade Zahl und a displaystyle a nbsp eine beliebige ganze Zahl die teilerfremd zu n displaystyle n nbsp ist dann kann das Jacobi Symbol durch a n sgn p a n displaystyle left frac a n right operatorname sgn pi a n nbsp definiert werden Im Fall dass a displaystyle a nbsp ungerade ist gilt fur das Jacobi Symbol ebenfalls das quadratische Reziprozitatsgesetz 2 Literatur BearbeitenOswald Baumgart The Quadratic Reciprocity Law A Collection of Classical Proofs Birkhauser 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 demonstration de la loi de reciprocite de Legendre In Nouvelles Annales de Mathematiques 2e serie Band 11 1872 S 354 362 Online PDF Ferdinand Georg Frobenius Uber das quadratische Reziprozitatsgesetz In Sitzungsberichte der Koniglich Preussischen Akademie der Wissenschaften zu Berlin 1914 S 335 349 Online PDF Einzelnachweise Bearbeiten Volker Diekert Manfred Kufleitner Gerhard Rosenberger Diskrete algebraische Methoden de Gruyter 2013 S 42 Volker Diekert Manfred Kufleitner Gerhard Rosenberger Diskrete algebraische Methoden de Gruyter 2013 S 43 Weblinks Bearbeitenmathcam 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 Abgerufen von https de wikipedia org w index php title Lemma von Zolotareff amp oldid 205643326