Das quadratische Reziprozitätsgesetz, gelegentlich auch Gaußsches Reziprozitätsgesetz, ist ein grundlegendes Gesetz aus der Zahlentheorie, einem Teilgebiet der Mathematik. Es beschäftigt sich mit der Frage, ob es zu einer ungeraden Primzahl und einer durch diese nicht teilbaren ganzen Zahl eine Quadratzahl gibt, sodass die Differenz durch teilbar ist. Genau genommen gibt es, zusammen mit den beiden unten genannten Ergänzungssätzen, ein Verfahren an, um zu entscheiden, ob eine Zahl quadratischer Rest oder Nichtrest einer Primzahl ist. Die Entdeckung des quadratischen Reziprozitätsgesetzes durch Leonhard Euler und der Beweis durch Gauß (Disquisitiones Arithmeticae 1801, er hatte aber bereits 1796 einen Beweis) waren die Ausgangspunkte der Entwicklung der modernen algebraischen Zahlentheorie.

Um die genaue Aussage des quadratischen Reziprozitätsgesetzes zu verstehen, sind lediglich die Konzepte der Quadratzahlen, der Primzahlen und der Teilbarkeit ganzer Zahlen mit Rest vonnöten. Seine Formulierung beginnt mit der Auswahl zweier ungerader, ungleicher Primzahlen und , etwa und . Im Zentrum steht die folgende Fragestellung: Existiert eine Quadratzahl , sodass die Differenz teilt? (Mit den obigen Beispielwerten: Ist die Zahl für eine Quadratzahl durch teilbar?). Innerhalb dieser Fragestellung haben die beiden Primzahlen und eine unterschiedliche Stellung ( ist „Teiler“ und ist „Subtrahend“). Das Wort „Reziprozität“ (von „reziprok“, also wechselseitig) deutet nun an, dass dieselbe Frage ebenfalls unter Vertauschung der Rollen beider Primzahlen gefragt werden kann: Gibt es also eine (zweite) Quadratzahl , sodass wiederum die Differenz teilt? Das quadratische Reziprozitätsgesetz formuliert eine einfache Regel, die die Lösbarkeit der zwei Aufgaben, die durch Vertauschen der Rollen beider Primzahlen entstehen, miteinander in Beziehung setzt. Es unterscheidet: Hat mindestens eine der beiden Primzahlen und bei Teilung durch den Rest , so ist die eine Frage genau dann mit „Ja“ zu beantworten, wenn es auch die andere ist. Zum Beispiel hat bei Teilung durch den Rest . Mit den Wahlen , und erhält man und , wobei Ersteres durch und Letzteres durch teilbar ist (es ist ). Also lässt sich die Frage im Falle von und wechselseitig mit „Ja“ beantworten, wie es das Reziprozitätsgesetz vorhersagt. Im Gegensatz dazu existieren keine Quadratzahlen und , sodass durch und durch teilbar ist. Haben hingegen beide Primzahlen und bei Teilung durch den Rest , so ist stets genau eine der Fragen mit „Ja“ zu beantworten. Beispiel und : Es ist durch teilbar, es gibt aber keine Quadratzahl , sodass durch teilbar ist. Es haben sowohl als auch bei Division mit den Rest .

In Termen des Legendre-Symbols drückt sich dieser Sachverhalt für ungerade Primzahlen aus durch

Das quadratische Reziprozitätsgesetz ist aus mathematischer Sicht unter anderem von Interesse, da es einen Zusammenhang zwischen scheinbar verschiedenen Fragestellungen herstellt. Das führt dazu, dass die Lösung einer mitunter sehr schweren Aufgabe auf das Lösen einer leichten Aufgabe zurückgeführt werden kann, weshalb es für konkrete Berechnungen von Nutzen ist. Zahlreiche Anwendungen findet es in der Zahlentheorie, der Theorie diophantischer Gleichungen, aber auch in praktischen Gebieten wie der Kryptographie.

Gauß selbst hat acht methodisch verschiedene Beweise für das quadratische Reziprozitätsgesetz vorgelegt. Da er die Bedeutung des Resultats bereits als außerordentlich hoch erkannte, bezeichnete er sein Resultat als „Fundamentaltheorem“ bzw. „Theorema aureum“ (deutsch: „Goldener Satz“) der Zahlentheorie. Die Bezeichnung „Reziprozitätsgesetz“ geht indes auf Adrien-Marie Legendre zurück, der im Jahr 1785 einen unvollständigen Beweis lieferte. Spätere (vollständige) Beweise stammen unter anderem von Gotthold Eisenstein, Peter Gustav Lejeune Dirichlet, Richard Dedekind und Jegor Iwanowitsch Solotarjow. Bis heute sind mehr als 300 verschiedene Beweise publiziert worden. Trotz elementarer Beweise liegt das Wesen der „Reziprozität“, wie schon Gauß vermutete, relativ tief, nämlich in der Primfaktorzerlegung in den Kreisteilungskörpern.

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, das kubische Reziprozitätsgesetz, behandelte Gotthold Eisenstein, den Fall vierten Grades Gauß, wobei jedoch Carl Gustav Jacobi den ersten vollständigen Beweis vorlegte. Eine moderne, sehr viel tiefer liegende, Verallgemeinerung findet sich in den Grundlagen der Klassenkörpertheorie.

Fragestellung und Grundlagen

Das quadratische Reziprozitätsgesetz motiviert sich aus der Aufgabe, schnell über die Lösbarkeit quadratischer Kongruenzen entscheiden zu können. Im Falle von Primzahlen entspricht dies einer quadratischen Gleichung über einem endlichen Körper. Für ein genaues Verständnis seiner Aussage werden die folgenden Grundlagen zusammengefasst.

Endliche Körper

In der Mathematik bezeichnet ein Körper eine Menge, innerhalb der, 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. Insbesondere 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 Forderung ist, dass keine der erlaubten Rechenoperationen dazu führt, dass man die den Körper definierende Zahlenmenge verlässt. So ist es etwa 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. Grundsätzlich ist das Konzept einer Quadratwurzel in einem Körper aber indirekt erklärt, da die umgekehrte Operation, nämlich die Multiplikation einer Zahl mit sich selbst, in Körpern definiert ist, wobei die Existenz eine andere Frage ist.

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 nichtrationale Zahlen zu hinzunehmen, um größere Körper zu konstruieren. Ein Beispiel ist der Körper , der aus allen Zahlen mit besteht (siehe auch: Zahlkörper, und zum Beispiel Quadratischer Zahlkörper).Peter Bundschuh: Einführung in die Zahlentheorie, 6. Auflage, Springer, S. 71–72. Rechnungen wie

sind Prototypen für die Abgeschlossenheit der vier Grundrechenarten in . Es 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 ElementeDie neutralen Elemente der Addition bzw. Multiplikation werden in allgemeinen Körpern weiterhin meistens mit und bezeichnet. Entsprechend können erneut die Benennungen usw. durch arabische Ziffern benutzt werden, obwohl sich das Rechnen in anderen Körpern in manchen Fällen von jenem aus den reellen Zahlen „unterscheidet“. Streng genommen müssten daher Notationen wie benutzt werden, um die Zugehörigkeit zum Körper zu erklären.

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 , sodass

in erstmals erfüllt ist.Da es nur endlich viele Elemente im Körper gibt, kommt irgendwann der Punkt, dass die Folge irgendeiner Wiederholung unterworfen ist. Etwa könnte gelten. Da in Körpern nun aber auch die Subtraktion erlaubt ist, folgte damit . Diese Kennzahl wird Charakteristik des Körpers genannt, also . Sie ist stets eine Primzahl,Siegfried Bosch: Algebra, Springer Spektrum, 8. Auflage, S. 87–88. denn wäre zum Beispiel zusammengesetzt, so müsste sein, und es wäre bereits oder , also , 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, und (d. h. alle ganzen Vielfache der Zahl ). Dabei bedeuten die Über-Striche, dass alle Zahlen, die bei Division mit den entsprechenden Rest haben, gemeinsam bzw. gebündelt betrachtet werden. Etwa besteht

aus genau jenen Zahlen, die bei Division mit den Rest haben. Die Zahlen von bis sind ferner lediglich Repräsentanten einer ganzen Restklasse,Friedrich Ischebeck: Einladung zur Zahlentheorie, BI Wissenschaftsverlag, S. 53. zum Beispiel gelten die Gleichheiten

Die jeweiligen Repräsentanten ergeben bei Division durch alle denselben Rest und gehören so zur selben Restklasse. Man sieht damit, dass additive Vielfache von in diesem Beispiel für die Zugehörigkeit zur gleichen Restklasse stets keine Rolle spielen. Mit anderen Worten: Während eine ganze Zahl stets erst durch ihre Zählgröße vollständig bestimmt ist, handelt es sich bei Restklassen um reduzierte Zahlen. Nur noch der Rest ist entscheidend, nicht mehr die Größe.

Mit Restklassen modulo kann nun in den vier Grundrechenarten gerechnet werden. Dabei gelten im Grunde dieselben Regeln wie beim Rechnen in den ganzen Zahlen : Zum Beispiel ist (Bedeutung: Die Summe zweier beliebiger Zahlen mit Rest bei Division durch hat stets Rest bei Division durch , etwa oder .) (Bedeutung: Die Differenz zweier beliebiger Zahlen mit dem selben Rest, etwa , bei Division durch , ist stets durch teilbar, hat also Rest .) (Bedeutung: Das Produkt zweier beliebiger Zahlen mit Rest bzw. bei Division durch hat stets Rest bei Division durch , etwa oder ) Wichtig ist an dieser Stelle, zu zeigen, dass dies wohldefiniert ist, dass 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 (vgl. obiges Beispiel)

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 die folgende: Für ein Element , das man invertieren möchte, betrachtet man alle möglichen Vielfachen (ungleich Null):