Benutzer:Googolplexian1221/Quadratisches Reziprozitätsgesetz

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

Das quadratische Reziprozitätsgesetz gibt, zusammen mit den beiden unten genannten Ergänzungssätzen, ein Verfahren an, um das Legendre-Symbol zu berechnen und damit zu entscheiden, ob eine Zahl quadratischer Rest oder Nichtrest einer (anderen) Zahl ist. Die Entdeckung des quadratischen Reziprozitätsgesetzes durch Euler und der Beweis durch Gauß (Disquisitiones Arithmeticae 1801, er hatte aber bereits 1796 einen Beweis) waren die Ausgangspunkte der Entwicklung der modernen Zahlentheorie. Obwohl es elementare Beweise des Reziprozitätsgesetzes gibt, liegt dessen Wesen relativ tief, nämlich in der Primfaktorzerlegung in den Kreisteilungskörpern mit einer primitiven Einheitswurzel . Gauß selbst hat mehrere methodisch verschiedene Beweise vorgelegt.

Das quadratische Reziprozitätsgesetz stellt für zwei ungerade, ungleiche Primzahlen und einen Zusammenhang zwischen den Fragen her, ob eine Quadratzahl existiert, sodass die Zahl teilt, und umgekehrt eine Quadratzahl existiert, sodass die Zahl teilt. Das Wort „Reziprozität“ bezieht sich darauf, dass die Rollen von und dabei jeweils vertauscht werden.

Das quadratische Reziprozitätsgesetz macht Aussagen über die Lösbarkeit quadratischer Gleichungen in der modularen Arithmetik, die Frage nach der Lösbarkeit von Gleichungen höheren Grades führt auf die höheren Reziprozitätsgesetze, was eine der treibenden Kräfte der algebraischen Zahlentheorie seit Gauß war. Den Fall dritten Grades (kubisches Reziprozitätsgesetz) behandelte Gotthold Eisenstein, den Fall vierten Grades (biquadratisches Reziprozitätsgesetz) Gauß.

Einführung und Aussage

[Bearbeiten | Quelltext bearbeiten]

Endliche Körper

[Bearbeiten | Quelltext bearbeiten]

In der Mathematik bezeichnet ein Körper eine Menge, innerhalb derer, einfach gesprochen, mit den vier Grundrechenarten gerechnet werden kann. Dabei sollen die aus der Schulmathematik bekannten Regeln des Kommutativgesetzes (Vertauschbarkeit bei „Plus“ und „Mal“), Assoziativgesetzes (Vertauschbarkeit von Klammern bei „nur Plus“ oder „nur Mal“) und Distributivgesetzes („Ausklammern“ und „Ausmultiplizieren“) gelten. Außerdem muss stets das Element (neutrales Element der Addition) und (neutrales Element der Multiplikation) Teil eines Körpers sein. Ferner soll durch jede Zahl ungleich der dividiert werden können. Wichtige Beispiele sind der Körper der reellen Zahlen (Bezeichnung: ) oder der Körper der rationalen Zahlen (Bezeichnung: ).

Eine wichtige Voraussetzung ist stets, dass jede erlaubte Rechenoperation nicht dazu führt, dass man die den Körper definierende Zahlenmenge verlässt. In etwa ist es in Körpern im Allgemeinen nicht erlaubt, Quadratwurzeln zu ziehen. Es ist ein Element von , kurz , aber ist eine irrationale Zahl, also . Ähnlich besitzt keine Quadratwurzel in den reellen Zahlen.

Eine Fragestellung aus der Algebra ist, wie Körper aussehen können, also in welchen Typen von Mengen ein „abgeschlossenes Rechnen“ möglich ist. So kann man weitere nicht rationale Zahlen zu hinzunehmen, und größere Körper konstruieren. Ein Beispiel ist der Körper , der aus allen Zahlen mit besteht (siehe auch: Zahlkörper, und zum Beispiel Quadratischer Zahlkörper). Dies ist, zusammen mit und , ein weiteres Beispiel für einen Körper mit unendlich vielen Elementen. Bemerkenswert ist es aber, dass auch Körper mit nur endlich vielen Elementen existieren. Das Rechnen in diesen Bereichen weicht, obwohl die Gesetze letztlich die gleichen sind, von der „klassischen Anschauung“ ab. Das beginnt damit, dass die Elemente

nicht alle verschieden sein können, da nur endlich viele Elemente hat. Da man stets hat (sonst wäre , und diesen trivialen Fall schließt man aus), gibt es damit eine kleinste natürliche Zahl , so dass

in erstmals erfüllt ist. Diese Kennzahl wird auch als die Charakteristik des Körpers bezeichnet, also . Sie ist stets eine Primzahl, denn wäre zum Beispiel zusammengesetzt, so müsste sein, und es wäre bereits oder , was der Annahme wegen der Minimalität der Charakteristik direkt widerspräche.

Um das Rechnen in endlichen Körpern genau zu verstehen, ist der Umgang mit Resten bei Divisionsaufgaben notwendig. Nichttriviale Reste entstehen bei Divisionen, die nicht aufgehen. Etwa ist geteilt durch gleich mit Rest . In den einfachsten Beispielen endlicher Körper wird mit genau diesen Resten gerechnet. Dies kann anhand eines Beispiels demonstriert werden: Es gibt genau fünf mögliche Reste bei der Division durch , und diese korrespondieren zu

mit Menge der ganzen Zahlen.

Dabei bedeuten die Über-Striche, dass alle Zahlen, welche bei Division mit den entsprechenden Rest haben, gemeinsam bzw. gebündelt betrachtet werden. Etwa ist

Die Zahlen von bis sind ferner lediglich Repräsentanten einer ganzen Restklasse, zum Beispiel gelten die Gleichheiten

Die jeweiligen Repräsentanten ergeben bei Division durch alle den selben Rest , und gehören so zur selben Restklasse. Man sieht damit, dass Vielfache von in diesem Beispiel für die Zugehörigkeit zur gleichen Restklasse stets keine Rolle spielen. Mit Restklassen kann nun in den vier Grundrechenarten gerechnet werden. Dabei gelten im Grunde die selben Regeln wie beim Rechnen in den ganzen Zahlen : Zum Beispiel ist

usw. Wichtig ist an dieser Stelle, zu zeigen, dass dies wohldefiniert ist, also bei der Auswahl anderer Repräsentanten, stets das gleiche Ergebnis herauskommt. Da die Differenz zweier Repräsentanten aber stets durch teilbar ist, liegt dies auf der Hand: Zum Beispiel ist

aber auch

Ganz ähnliche Überlegungen gelten bei der Wohldefiniertheit der Multiplikation.

Auch die Division ist innerhalb von möglich (schließt man aus), denn um allgemein dividieren zu können, ist für jedes lediglich die Existenz eines Inversen mit

vonnöten (wie etwa und im Fall der rationalen Zahlen). Für den Nachweis, dass es stets ein Inverses gibt, ist entscheidend, dass eine Primzahl ist: Teilt eine Primzahl ein Produkt zweier ganzer Zahlen, muss bereits mindestens einer der Faktoren durch diese teilbar sein. Hat man dies zur Hand, ist die Argumentation ein simples Schubfachprinzip: Für ein Element , das man invertieren möchte, betrachtet man alle möglichen Vielfachen (ungleich Null):

Die Restklasse taucht in dieser Liste nicht auf, denn keine der Zahlen ist durch teilbar. Ferner sind alle Einträge der Liste paarweise verschieden, denn es ist gleichbedeutend damit, dass . Die Differenz liegt nach Wahl der oberen Vorfaktor-Repräsentanten im Intervall , und nur die ist dort durch teilbar. Also ist . Es muss nach dem Schubfachprinzip also die Restklasse irgendwo in der oberen Liste auftauchen und ein Inverses ist gefunden. Zum Beispiel ist ein Inverses zu , da . Da im Wesentlichen „weiterhin in den ganzen Zahlen gerechnet wird“, bleiben Kommutativgesetz, Assoziativgesetz und Distributivgesetz erhalten, womit die Restklassenmenge in der Tat einen Körper bildet.

Diese ganze Argumentation beschränkt sich nicht auf die Primzahl , sondern es kann zu jeder Primzahl ein entsprechender endlicher Körper angegeben werden:

usw. Dabei müssen die durch die Über-Striche angedeuteten Restklassen natürlich stets auf die betroffene Primzahl angewendet werden.

Modulare Arithmetik

[Bearbeiten | Quelltext bearbeiten]

Die modulare Arithmetik bezeichnet im Wesentlichen das Rechnen mit Restklassen, und damit verbundene Themenfelder, wie etwa Gleichungen. Für eine natürliche Zahl , den „Modul“, bezeichnet man zwei ganze Zahlen und als kongruent modulo , falls deren Differenz teilt, also

Man schreibt in diesem Falle die Kongruenz auch als

gelesen als: „ kongruent modulo “. Sind zwei ganze Zahlen kongruent modulo , gehören sie zur selben Restklasse bei der Division durch (und umgekehrt). Man schreibt dann , und mit Restklassen kann wie gewohnt gerechnet werden (siehe vorheriger Abschnitt in Bezug auf endliche Körper). Ist eine Primzahl, so bildet die Menge der Restklassen modulo einen Körper . Ist hingegen zusammengesetzt, handelt es sich lediglich um einen Ring.

Quadratische Gleichungen

[Bearbeiten | Quelltext bearbeiten]

Eine quadratische Gleichung ist eine Gleichung der Form

mit einer Unbekannten . Es handelt sich also um einen Spezialfall einer algebraischen Gleichung, bei der die Unbekannte einfach mit sich selbst multipliziert werden kann. Grundsätzlich können algebraische Gleichungen, die sich auf der Anwendung der vier Grundrechenarten zusammensetzen, über Körpern studiert werden, wo all diese Rechenoperationen einen Sinn ergeben. In der Schulmathematik wird beispielsweise der Körper zugrunde gelegt. Es ist also , und man ist an Lösungen in den reellen Zahlen interessiert. Allerdings kann die obere Gleichung, falls auch lediglich nur über den rationalen Zahlen betrachtet werden. Zum Beispiel hat die Gleichung über den reellen Zahlen die Lösungen , aber über den rationalen Zahlen keine Lösung.

In Algebra und Zahlentheorie ist man vor allen Dingen nach einem schnellen Verfahren interessiert, zu entscheiden, ob eine algebraische Gleichung über ihrem Körper überhaupt lösbar ist. Es bietet sich an, hier über „Kennzahlen“ zu arbeiten. Der oberen quadratischen Gleichung kann die Zahl

zugeordnet werden, die sich aus den Koeffizienten und schnell berechnen lässt. Diese wird auch als Diskriminante der Gleichung bezeichnet. Über die Mitternachtsformel, welche potenzielle Lösungen als

identifiziert, erkennt man, dass die Gleichung

  • genau dann zwei verschiedene Lösungen besitzt, falls ein Quadrat im zugrunde liegenden Körper ist (also der Term im Körper enthalten ist),
  • genau dann eine (doppelte) Lösungen besitzt, falls ,
  • genau dann keine Lösung besitzt, falls kein Quadrat im zugrunde liegenden Körper ist.

Im Fall des Körpers sind also lediglich die Fälle , und zu unterscheiden, da eine reelle Zahl ungleich genau dann eine Quadratwurzel in hat, wenn sie positiv ist. Bei den rationalen Zahlen hingegen ist die Unterscheidung subtiler. Wie bereits oben gesehen, hat die Gleichung keine rationalen Lösungen, und in der Tat ist ihre Diskriminante zwar positiv, aber kein Quadrat einer rationalen Zahl.

Neben den reellen oder rationalen Zahlen, können quadratische Gleichugen des Typs

über dem Körper studiert werden. Das quadratische Reziprozitätsgesetz kann dabei helfen, schnell zu entscheiden, ob Lösbarkeit vorliegt, oder nicht.

Das Legendre-Symbol

[Bearbeiten | Quelltext bearbeiten]

Um zu entscheiden, ob eine quadratische Gleichung mit über mit einer Primzahl lösbar ist, reicht es aus, zu entscheiden, ob die Diskriminante ein Quadrat in ist. Der Fall spielt eine Sonderrolle, da in der Mitternachtsformel durch geteilt wird, womit man im Fall aber durch Null teilen würde, was nicht zulässig ist. Dies motiviert den Begriff des quadratischen Rests. Damit sind jene Elemente des endlichen Körpers gemeint, die ungleich Null sind und durch Quadrieren eines (anderen) Elements aus entstehen. Mit anderen Worten, eine zu teilerfremde Zahl ist genau dann quadratischer Rest modulo , falls eine Quadratzahl existiert, so dass durch teilbar ist. Elemente aus , die nicht Null und keine quadratischen Reste sind, bezeichnet man auch als quadratische Nichtreste.

Ist zum Beispiel , so bekommt man durch Quadrieren der Restklassen modulo :

Es sind also die Elemente und die quadratischen Reste modulo . Somit ist zum Beispiel die Gleichung

nicht in lösbar, denn ist quadratischer Nichtrest modulo . Im Gegensatz dazu ist in lösbar, denn es ist ein quadratischer Rest modulo . In der Tat ist etwa eine Lösung, denn .

Adrien-Marie Legendre

Aus mathematischer Sicht macht es Sinn, die quadratischen Reste von den Nichtresten zu „trennen“. Dabei wird der eine besondere Rolle zugeordnet. Zu diesem Zweck definiert man das Legendre-Symbol, benannt nach Adrien-Marie Legendre. Dieses ist eine mathematische Funktion mit Definitionsbereich und Zielmenge , die einen quadratischen Rest den Wert („positiv“), einem Nichtrest („negativ“) und der schlicht den Wert zuordnet. In Symbolen setzt man:

Es ist nicht als Bruch zu verstehen. In der Literatur wird deshalb gelegentlich auch die Notation genutzt, um Verwechslungen zu vermeiden. Auf natürliche Weise kann das Legendre-Symbol auch als Funktion auf den ganzen Zahlen aufgefasst werden, die dann, wegen ihrer ursprünglichen Definition auf Restklassen, -periodisch ist. Es ist dann , und letzterer Ausdruck wird am häufigsten verwendet.

Bemerkenswerterweise spaltet sich die Menge der quadratischen Reste und Nichtreste in genau zwei gleich große Mengen mit der Anzahl der Elemente , wenn die Primzahl ungerade ist. Wie oben gesehen im Fall , sind es die Mengen und mit je drei Elementen. Zudem gelten die folgenden sehr wichtigen Regeln:

  • Das Produkt zweier quadratischer Reste ist wieder ein quadratischer Rest.
  • Das Produkt eines quadratischen Rests und eines quadratischen Nichtrests ist ein quadratischer Nichtrest.
  • Das Produkt zweier quadratischer Nichtreste ist ein quadratischer Rest.

Anstatt in Resten und Nichtresten zu denken, kann durch diese Regeln auch zu und übergegangen werden. Analog werden in dieser Sichtweise die Regeln , und respektiert. Das Legrendre-Symbol dient nun als ein „Übersetzer“ zum Beispiel der Regel „Nichtrest mal Nichtrest gleich Rest“ in „negativ mal negativ gleich positiv“. In mathematischer Sprache handelt es sich um einen sog. Gruppenhomomorphismus

Aussage des quadratischen Reziprozitätsgesetzes

[Bearbeiten | Quelltext bearbeiten]

Im Folgenden bezeichnet mit einer ganzen Zahl und einer Primzahl das Legendre-Symbol.

Das quadratische Reziprozitätsgesetz besagt, dass für zwei verschiedene ungerade Primzahlen  und  gilt:

1. Ergänzungssatz: Für jede ungerade Primzahl  gilt:

2. Ergänzungssatz: Für jede ungerade Primzahl  gilt:

Sind und zwei verschiedene ungerade Primzahlen, so gilt folglich:

Aus folgt nämlich .

Erstmals entdeckt wurde das quadratische Reziprozitätsgesetz von Leonhard Euler, der es durch empirische Nachforschungen als richtig befand, jedoch keinen Beweis vorlegen konnte.

Noch im selben Jahrhundert wurde es von Legendre wiederentdeckt, und 1785 veröffentlicht. Legendre gab zudem einen unvollständigen Beweis an.

Den ersten vollständigen Beweis lieferte Carl Friedrich Gauß 1801 in seiner für die moderne Zahlentheorie wegweisenden Schrift Disquisitiones Arithmeticae. Jedoch hatte Gauß nachweislich bereits 1796, im Alter von Neunzehn Jahren, über einen solchen verfügt.

lösbar ist. Dazu berechnet man

(das Legendre-Symbol ist multiplikativ im oberen Argument).

Der erste Faktor lässt sich mit Hilfe des zweiten Ergänzungssatzes zu bestimmen. Um den zweiten Faktor zu berechnen, wendet man das Reziprozitätsgesetz an:

Hier wurde beim zweiten Gleichheitszeichen verwendet, analog dazu beim vorletzten.

Setzt man nun beide Faktoren zusammen, so ergibt sich

Damit weiß man, dass die obige Kongruenz eine Lösung besitzt, und wegen gilt tatsächlich .

  • Es ist zu prüfen, ob die Kongruenz

lösbar ist. Dazu berechnet man wieder

und kann wie oben die beiden Faktoren mit dem Reziprozitätsgesetz weiter vereinfachen:

(im letzten Schritt wurde mit verwendet)

und

Setzt man alles zusammen, so ergibt sich

und damit die Erkenntnis, dass die obige Kongruenz keine Lösung besitzt.

Analoga und Verallgemeinerungen

[Bearbeiten | Quelltext bearbeiten]

Kubisches Reziprozitätsgesetz

[Bearbeiten | Quelltext bearbeiten]

Biquadratisches Reziprozitätsgesetz

[Bearbeiten | Quelltext bearbeiten]

Artinsches Reziprozitätsgesetz

[Bearbeiten | Quelltext bearbeiten]

Analogon zu elliptischen Kurven

[Bearbeiten | Quelltext bearbeiten]

Effiziente Berechnung des Legendre-Symbols

[Bearbeiten | Quelltext bearbeiten]

Der hier aufgezeigte Berechnungsweg besitzt den Nachteil, die Primfaktorzerlegung des Zählers des Legendre-Symbols bestimmen zu müssen. Es gibt ein effizienteres Verfahren, das ähnlich wie der Euklidische Algorithmus abläuft und ohne diese Faktorisierung auskommt. Dabei wird das Jacobi-Symbol, eine Verallgemeinerung des Legendre-Symbols, benutzt, für das das quadratische Reziprozitätsgesetz immer noch gültig ist.

  • Lemma von Zolotareff, eine Beweisvariante für das quadratische Reziprozitätsgesetz mit Hilfe von Permutationen
  • Oswald Baumgart: The quadratic reciprocity law. A collection of classical proofs, Birkhäuser 2015
  • K. Chandrasekharan: Introduction to Analytic Number Theory. Springer Verlag, Grundlehren der mathematischen Wissenschaften 148, ISBN 3540041419, Kap. V: The law of quadratic reciprocity.
  • Eugen Netto (Hrsg.): Sechs Beweise des Fundamentaltheorems über quadratische Reste von Carl Friedrich Gauß. Verlag Wilhelm Engelmann, Leipzig 1901, digitalisierte Version.
  • Franz Lemmermeyer: Reciprocity Laws. From Euler to Eisenstein. Springer Verlag, eingeschränkte Vorschau in der Google-Buchsuche.


Kategorie:Zahlentheoretischer Algorithmus Kategorie:Satz (Zahlentheorie)