Quadratisches Reziprozitätsgesetz

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 ganzen Zahl ${\displaystyle a}$ und einer ungeraden Primzahl ${\displaystyle p}$ eine Quadratzahl ${\displaystyle m^{2}}$ gibt, sodass die Differenz ${\displaystyle m^{2}-a}$ durch ${\displaystyle p}$ 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 quadratische 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 ${\displaystyle p}$ und ${\displaystyle q}$, etwa ${\displaystyle p=5}$ und ${\displaystyle q=19}$. Im Zentrum steht die folgende Fragestellung:

Existiert eine Quadratzahl ${\displaystyle m^{2}}$, sodass ${\displaystyle p}$ die Differenz ${\displaystyle m^{2}-q}$ teilt? (Mit den oberen Beispielwerten: Ist die Zahl ${\displaystyle m^{2}-19}$ für eine Quadratzahl ${\displaystyle m^{2}}$ durch ${\displaystyle 5}$ teilbar?).

Innerhalb dieser Fragestellung haben die beiden Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$ eine unterschiedliche Stellung (${\displaystyle p}$ ist „Teiler“ und ${\displaystyle q}$ 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 ${\displaystyle n^{2}}$, sodass ${\displaystyle q}$ wiederum die Differenz ${\displaystyle n^{2}-p}$ 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 ${\displaystyle p}$ und ${\displaystyle q}$ bei Teilung durch ${\displaystyle 4}$ den Rest ${\displaystyle 1}$, so ist die eine Frage genau dann mit „Ja“ zu beantworten, wenn es auch die andere ist. Zum Beispiel hat ${\displaystyle p=5}$ bei Teilung durch ${\displaystyle 4}$ den Rest ${\displaystyle 1}$. Mit den Wahlen ${\displaystyle q=19}$, ${\displaystyle m^{2}=2^{2}=4}$ und ${\displaystyle n^{2}=9^{2}=81}$ erhält man ${\displaystyle 4-19=-15}$ und ${\displaystyle 81-5=76}$, wobei Ersteres durch ${\displaystyle 5}$ und Letzteres durch ${\displaystyle 19}$ teilbar ist (es ist ${\displaystyle 76=4\cdot 19}$). Also lässt sich die Frage im Falle von ${\displaystyle p=5}$ und ${\displaystyle q=19}$ wechselseitig mit „Ja“ beantworten, wie es das Reziprozitätsgesetz vorhersagt. Im Gegensatz dazu existieren keine Quadratzahlen ${\displaystyle m^{2}}$ und ${\displaystyle n^{2}}$, sodass ${\displaystyle m^{2}-3}$ durch ${\displaystyle 5}$ und ${\displaystyle n^{2}-5}$ durch ${\displaystyle 3}$ teilbar ist.
• Haben hingegen beide Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$ bei Teilung durch ${\displaystyle 4}$ den Rest ${\displaystyle 3}$, so ist stets genau eine der Fragen mit „Ja“ zu beantworten. Beispiel ${\displaystyle p=3}$ und ${\displaystyle q=7}$: Es ist ${\displaystyle 1^{2}-7=-6}$ durch ${\displaystyle 3}$ teilbar, es gibt aber keine Quadratzahl ${\displaystyle n^{2}}$, sodass ${\displaystyle n^{2}-3}$ durch ${\displaystyle 7}$ teilbar ist. Es haben sowohl ${\displaystyle 3}$ als auch ${\displaystyle 7}$ bei Division mit ${\displaystyle 4}$ den Rest ${\displaystyle 3}$.

Das quadratische Reziprozitätsgesetz ist aus mathematischer Sicht unter anderem von Interesse, da es kausale Zusammenhänge zwischen scheinbar völlig verschiedenen Fragestellungen aufbaut. 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 ${\displaystyle 0}$ (neutrales Element der Addition) und ${\displaystyle 1}$ (neutrales Element der Multiplikation) Teil eines Körpers sein. Insbesondere soll durch jede Zahl ungleich der ${\displaystyle 0}$ dividiert werden können. Wichtige Beispiele sind der Körper der reellen Zahlen (Bezeichnung: ${\displaystyle \mathbb {R} }$) oder der Körper der rationalen Zahlen (Bezeichnung: ${\displaystyle \mathbb {Q} }$).

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 ${\displaystyle 2}$ ein Element von ${\displaystyle \mathbb {Q} }$, kurz ${\displaystyle 2\in \mathbb {Q} }$, aber ${\displaystyle {\sqrt {2}}}$ ist eine irrationale Zahl, also ${\displaystyle {\sqrt {2}}\notin \mathbb {Q} }$. Ähnlich besitzt ${\displaystyle -1}$ 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 ${\displaystyle \mathbb {Q} }$ hinzunehmen, um größere Körper zu konstruieren. Ein Beispiel ist der Körper ${\displaystyle \mathbb {Q} ({\sqrt {2}})}$, der aus allen Zahlen ${\displaystyle x+{\sqrt {2}}y}$ mit ${\displaystyle x,y\in \mathbb {Q} }$ besteht (siehe auch: Zahlkörper, und zum Beispiel Quadratischer Zahlkörper).^[1] Rechnungen wie

${\displaystyle (-2+3{\sqrt {2}})+(3-{\sqrt {2}})=1+2{\sqrt {2}},\quad (1-{\sqrt {2}})\cdot (2+{\tfrac {3}{7}}{\sqrt {2}})={\tfrac {8}{7}}-{\tfrac {11}{7}}{\sqrt {2}},\quad {\tfrac {3+{\sqrt {2}}}{4-2{\sqrt {2}}}}=2+{\tfrac {5}{4}}{\sqrt {2}}}$

sind Prototypen für die Abgeschlossenheit der vier Grundrechenarten in ${\displaystyle \mathbb {Q} ({\sqrt {2}})}$. Es ist ${\displaystyle \mathbb {Q} ({\sqrt {2}})}$, zusammen mit ${\displaystyle \mathbb {Q} }$ und ${\displaystyle \mathbb {R} }$, ein weiteres Beispiel für einen Körper mit unendlich vielen Elementen. Bemerkenswert ist es aber, dass auch Körper ${\displaystyle \mathbb {K} }$ 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^{[Anm. 1]}

${\displaystyle 1=1,\qquad 1+1=2,\qquad 1+1+1=3,\qquad 1+1+1+1=4,\qquad \cdots }$

nicht alle verschieden sein können, da ${\displaystyle \mathbb {K} }$ nur endlich viele Elemente hat. Da man stets ${\displaystyle 0\not =1}$ hat (sonst wäre ${\displaystyle \mathbb {K} =\{0\}}$, und diesen trivialen Fall schließt man aus), gibt es damit eine kleinste natürliche Zahl ${\displaystyle p}$, sodass

${\displaystyle \underbrace {1+1+\cdots +1} _{p-{\text{mal}}}=0}$

in ${\displaystyle \mathbb {K} }$ erstmals erfüllt ist.^{[Anm. 2]} Diese Kennzahl wird Charakteristik des Körpers ${\displaystyle \mathbb {K} }$ genannt, also ${\displaystyle \mathrm {char} (\mathbb {K} )=p}$. Sie ist stets eine Primzahl,^[2] denn wäre zum Beispiel ${\displaystyle \mathrm {char} (\mathbb {K} )=2\cdot 3}$ zusammengesetzt, so müsste ${\displaystyle 2\cdot 3=0}$ sein, und es wäre bereits ${\displaystyle 2=1+1=0}$ oder ${\displaystyle 3=1+1+1=0}$, also ${\displaystyle \mathrm {char} (\mathbb {K} )\leq 3}$, was der Annahme ${\displaystyle \mathrm {char} (\mathbb {K} )=6}$ 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 ${\displaystyle 19}$ geteilt durch ${\displaystyle 5}$ gleich ${\displaystyle 3}$ mit Rest ${\displaystyle 4}$. 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 ${\displaystyle 5}$, und diese korrespondieren zu

${\displaystyle \left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}}\right\}=\{0+5\mathbb {Z} ,1+5\mathbb {Z} ,2+5\mathbb {Z} ,3+5\mathbb {Z} ,4+5\mathbb {Z} \}}$

mit ${\displaystyle \mathbb {Z} =}$ Menge der ganzen Zahlen, und ${\displaystyle 5\mathbb {Z} =\{\ldots ,-10,-5,0,5,10,\ldots \}}$ (d. h. alle ganzen Vielfache der Zahl ${\displaystyle 5}$). Dabei bedeuten die Über-Striche, dass alle Zahlen, die bei Division mit ${\displaystyle 5}$ den entsprechenden Rest haben, gemeinsam bzw. gebündelt betrachtet werden. Etwa besteht

${\displaystyle {\overline {4}}:=4+5\mathbb {Z} =\{\ldots ,-6,-1,4,9,14,19,\ldots \}}$

aus genau jenen Zahlen, die bei Division mit ${\displaystyle 5}$ den Rest ${\displaystyle 4}$ haben. Die Zahlen von ${\displaystyle 0}$ bis ${\displaystyle 4}$ sind ferner lediglich Repräsentanten einer ganzen Restklasse,^[3] zum Beispiel gelten die Gleichheiten

${\displaystyle \cdots ={\overline {-6}}={\overline {-1}}={\overline {4}}={\overline {9}}={\overline {14}}={\overline {19}}=\cdots .}$

Die jeweiligen Repräsentanten ergeben bei Division durch ${\displaystyle 5}$ alle denselben Rest ${\displaystyle 4}$ und gehören so zur selben Restklasse. Man sieht damit, dass additive Vielfache von ${\displaystyle 5}$ 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 ${\displaystyle 5}$ kann nun in den vier Grundrechenarten gerechnet werden. Dabei gelten im Grunde dieselben Regeln wie beim Rechnen in den ganzen Zahlen ${\displaystyle \mathbb {Z} }$: Zum Beispiel ist

${\displaystyle {\overline {4}}+{\overline {4}}={\overline {8}}={\overline {3}}\quad }$ (Bedeutung: Die Summe zweier beliebiger Zahlen mit Rest ${\displaystyle 4}$ bei Division durch ${\displaystyle 5}$ hat stets Rest ${\displaystyle 3}$ bei Division durch ${\displaystyle 5}$, etwa ${\displaystyle 14+34=48}$ oder ${\displaystyle 29+4=33}$.)

${\displaystyle {\overline {4}}-{\overline {39}}={\overline {-35}}={\overline {0}}\quad }$ (Bedeutung: Die Differenz zweier beliebiger Zahlen mit dem selben Rest, etwa ${\displaystyle 4}$, bei Division durch ${\displaystyle 5}$, ist stets durch ${\displaystyle 5}$ teilbar, hat also Rest ${\displaystyle 0}$.)

${\displaystyle {\overline {2}}\cdot {\overline {3}}={\overline {6}}={\overline {1}}\quad }$ (Bedeutung: Das Produkt zweier beliebiger Zahlen mit Rest ${\displaystyle 2}$ bzw. ${\displaystyle 3}$ bei Division durch ${\displaystyle 5}$ hat stets Rest ${\displaystyle 1}$ bei Division durch ${\displaystyle 5}$, etwa ${\displaystyle 12\cdot 13=156}$ oder ${\displaystyle 2\cdot 33=66.}$)

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 ${\displaystyle 5}$ teilbar ist, liegt dies auf der Hand: Zum Beispiel ist (vgl. oberes Beispiel)

${\displaystyle {\overline {14}}+{\overline {34}}={\overline {48}}={\overline {3}}}$

aber auch

${\displaystyle {\overline {29}}+{\overline {4}}={\overline {33}}={\overline {3}}.}$

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

Auch die Division ist innerhalb von ${\displaystyle \left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}}\right\}}$ möglich (schließt man ${\displaystyle {\overline {0}}}$ aus), denn um allgemein dividieren zu können, ist für jedes ${\displaystyle a}$ lediglich die Existenz eines Inversen ${\displaystyle b}$ mit

${\displaystyle ab=1}$

vonnöten (wie etwa ${\displaystyle 3}$ und ${\displaystyle {\tfrac {1}{3}}}$ im Fall der rationalen Zahlen). Für den Nachweis, dass es stets ein Inverses gibt, ist entscheidend, dass ${\displaystyle 5}$ eine Primzahl ist: Teilt eine Primzahl ein Produkt ${\displaystyle mn}$ 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 ${\displaystyle {\overline {a}}\in \left\{{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}}\right\}}$, das man invertieren möchte, betrachtet man alle möglichen Vielfachen (ungleich Null):

${\displaystyle {\overline {1}}\cdot {\overline {a}},\quad {\overline {2}}\cdot {\overline {a}},\quad {\overline {3}}\cdot {\overline {a}},\quad {\overline {4}}\cdot {\overline {a}}.}$

Die Restklasse ${\displaystyle {\overline {0}}}$ taucht in dieser Liste nicht auf, denn keine der Zahlen ${\displaystyle 1a,2a,3a,4a}$ ist durch ${\displaystyle 5}$ teilbar.^{[Anm. 3]} Ferner sind alle Einträge der Liste paarweise verschieden, denn es ist ${\displaystyle {\overline {m}}\cdot {\overline {a}}={\overline {n}}\cdot {\overline {a}}}$ gleichbedeutend damit, dass ${\displaystyle ({\overline {m}}-{\overline {n}})\cdot {\overline {a}}={\overline {0}}}$, ergo ${\displaystyle 5|(m-n)a}$. Da ${\displaystyle a}$ nicht durch ${\displaystyle 5}$ teilbar ist, muss ${\displaystyle m-n}$ durch ${\displaystyle 5}$ teilbar sein. Die Differenz ${\displaystyle m-n}$ liegt nach Wahl der obigen Repräsentanten ${\displaystyle 1\leq m,n\leq 4}$ im Intervall ${\displaystyle -3\leq m-n\leq 3}$, und nur die ${\displaystyle 0}$ ist dort durch ${\displaystyle 5}$ teilbar. Also ist ${\displaystyle m=n}$. Es muss also die Restklasse ${\displaystyle {\overline {1}}}$ irgendwo in der obigen Liste auftauchen und ein Inverses ist gefunden.^{[Anm. 4]} Zum Beispiel ist ${\displaystyle {\overline {2}}}$ ein Inverses zu ${\displaystyle {\overline {3}}}$ modulo ${\displaystyle 5}$, da ${\displaystyle {\overline {2}}\cdot {\overline {3}}={\overline {6}}={\overline {1}}}$.^{[Anm. 5]} Da im Wesentlichen „weiterhin in den ganzen Zahlen gerechnet wird“, bleiben Kommutativgesetz, Assoziativgesetz und Distributivgesetz erhalten, womit die Restklassenmenge ${\displaystyle \mathbb {F} _{5}:=\left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}}\right\}}$ in der Tat einen Körper bildet.

Diese ganze Argumentation beschränkt sich nicht auf die Primzahl ${\displaystyle 5}$, sondern es kann zu jeder Primzahl ${\displaystyle p}$ ein entsprechender endlicher Körper angegeben werden:

${\displaystyle \mathbb {F} _{2}=\left\{{\overline {0}},{\overline {1}}\right\},\qquad \mathbb {F} _{3}=\left\{{\overline {0}},{\overline {1}},{\overline {2}}\right\},\qquad \mathbb {F} _{5}=\left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}}\right\},\qquad \mathbb {F} _{7}=\left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}}\right\},\qquad \mathbb {F} _{11}=\left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {10}}\right\},\qquad \ldots }$

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

Modulare Arithmetik

Die modulare Arithmetik bezeichnet im Wesentlichen das Rechnen mit Restklassen, und damit verbundene Themenfelder, wie etwa Gleichungen. Für eine natürliche Zahl ${\displaystyle N}$, den „Modul“,^[5] bezeichnet man zwei ganze Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ als kongruent modulo ${\displaystyle N}$, falls ${\displaystyle N}$ deren Differenz teilt, also in Zeichen

${\displaystyle N|(a-b).}$

Man schreibt in diesem Falle die Kongruenz auch als

${\displaystyle a\equiv b{\pmod {N}},}$

gelesen als: „${\displaystyle a}$ kongruent ${\displaystyle b}$ modulo ${\displaystyle N}$“. Zum Beispiel gilt

${\displaystyle 3\equiv 8{\pmod {5}},}$

denn es teilt ${\displaystyle 5}$ die Differenz ${\displaystyle 3-8=-5}$. Sind zwei ganze Zahlen kongruent modulo ${\displaystyle N}$, gehören sie zur selben Restklasse bei der Division durch ${\displaystyle N}$ (und umgekehrt). Man schreibt dann ${\displaystyle {\overline {a}}={\overline {b}}}$, und mit Restklassen kann wie gewohnt gerechnet werden (siehe vorheriger Abschnitt in Bezug auf endliche Körper). Ist ${\displaystyle N}$ eine Primzahl, so bildet die Menge der Restklassen modulo ${\displaystyle N}$ einen Körper ${\displaystyle \mathbb {F} _{N}}$. Ist ${\displaystyle N>1}$ hingegen zusammengesetzt, handelt es sich lediglich um einen kommutativen Ring.^{[6][Anm. 6]} Kommutative Ringe ähneln in ihren Eigenschaften den Körpern (algebraische Strukturen mit Addition und Multiplikation), jedoch ist nicht immer eine Division möglich. Ein Beispiel ist ${\displaystyle \mathbb {Z} /4\mathbb {Z} :=\left\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}}\right\}}$,^{[Anm. 7]} also die Menge der Restklassen modulo ${\displaystyle 4}$ (es ist ${\displaystyle 4}$ keine Primzahl!). Es ist hier keine Division durch ${\displaystyle {\overline {2}}}$ möglich, denn ${\displaystyle {\overline {2}}\cdot {\overline {2}}={\overline {4}}={\overline {0}}}$. Aus einer „Division“ beider Seiten durch ${\displaystyle {\overline {2}}}$ folgte dann ${\displaystyle {\overline {2}}={\overline {0}}}$, was nicht sein kann, da ${\displaystyle 2}$ nicht durch ${\displaystyle 4}$ teilbar ist. Elemente eines Rings, durch die trotzdem dividiert werden kann (dazu zählt immer die Eins), heißen auch Einheiten (des Rings).^[7] Die Einheiten des Rings der ganzen Zahlen ${\displaystyle \mathbb {Z} }$ sind ${\displaystyle \{\pm 1\}}$, und des Rings ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$ gleich ${\displaystyle \left\{{\overline {1}},{\overline {3}}\right\}}$ (wie gesehen, ist neben ${\displaystyle {\overline {0}}}$ auch ${\displaystyle {\overline {2}}}$ modulo ${\displaystyle 4}$ keine Einheit, denn durch beide Elemente kann nicht dividiert werden).

Quadratische Gleichungen

Eine quadratische Gleichung ist eine Gleichung der Form

${\displaystyle Q\colon \quad ax^{2}+bx+c=0,\qquad (a\not =0)}$

mit einer Unbekannten ${\displaystyle x}$. Es handelt sich also um einen Spezialfall einer algebraischen Gleichung, bei der die Unbekannte ${\displaystyle x}$ 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 ${\displaystyle \mathbb {R} }$ zugrunde gelegt. Es ist also ${\displaystyle a,b,c\in \mathbb {R} }$, und man ist an Lösungen ${\displaystyle x}$ von ${\displaystyle ax^{2}+bx+c=0}$ in den reellen Zahlen interessiert. Allerdings kann die obere Gleichung, falls ${\displaystyle a,b,c\in \mathbb {Q} }$ auch lediglich nur über den rationalen Zahlen betrachtet werden. Zum Beispiel hat die Gleichung ${\displaystyle x^{2}-2=0}$ über den reellen Zahlen die Lösungen ${\displaystyle x=\pm {\sqrt {2}}}$, aber über den rationalen Zahlen keine Lösung. In Algebra und Zahlentheorie ist man vor allen Dingen an 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 obigen quadratischen Gleichung kann die Zahl

${\displaystyle D_{Q}:=b^{2}-4ac}$

zugeordnet werden, die sich aus den Koeffizienten ${\displaystyle a,b}$ und ${\displaystyle c}$ schnell berechnen lässt. Diese wird auch als Diskriminante (lateinisch discriminare = unterscheiden) der Gleichung ${\displaystyle Q}$ bezeichnet. Über die Mitternachtsformel, die potenzielle Lösungen als

${\displaystyle x_{1,2}={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}}$

identifiziert,^{[Anm. 8]} erkennt man, dass die Gleichung ${\displaystyle Q}$ genau dann Lösungen im betreffenden Körper hat, falls es Sinn macht, die Quadratwurzel aus der Diskriminante zu ziehen. Genauer gilt: Es hat ${\displaystyle Q}$

• genau dann zwei verschiedene Lösungen, falls ${\displaystyle b^{2}-4ac\not =0}$ und ein Quadrat im zugrunde liegenden Körper ist (also der Term ${\displaystyle {\sqrt {b^{2}-4ac}}}$ im Körper enthalten ist und nicht gleich 0 ist),
• genau dann eine („doppelte“) Lösung, falls ${\displaystyle b^{2}-4ac=0}$ (denn es gilt stets ${\displaystyle \pm {\sqrt {0}}=\pm 0=0}$, und ${\displaystyle 0}$ ist immer Teil des Körpers),
• genau dann keine Lösung, falls ${\displaystyle b^{2}-4ac}$ kein Quadrat im zugrunde liegenden Körper ist.

Im Fall des Körpers ${\displaystyle \mathbb {R} }$ sind also lediglich die Fälle ${\displaystyle D_{Q}>0}$, ${\displaystyle D_{Q}=0}$ und ${\displaystyle D_{Q}<0}$ zu unterscheiden, da eine reelle Zahl ungleich ${\displaystyle 0}$ genau dann eine Quadratwurzel in ${\displaystyle \mathbb {R} }$ hat, wenn sie positiv ist. Bei den rationalen Zahlen hingegen ist die Unterscheidung subtiler. Wie bereits oben gesehen, hat die Gleichung ${\displaystyle x^{2}-2=0}$ keine rationalen Lösungen, und in der Tat ist ihre Diskriminante ${\displaystyle D=0^{2}-4\cdot 1\cdot (-2)=8}$ zwar positiv, aber kein Quadrat einer rationalen Zahl. Dies ist ein erster Hinweis darauf, dass die Arithmetik in den reellen Zahlen einfacher ist als jene in den rationalen Zahlen.

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

${\displaystyle {\overline {a}}x^{2}+{\overline {b}}x+{\overline {c}}={\overline {0}}\qquad ({\overline {a}},{\overline {b}},{\overline {c}}\in \mathbb {F} _{p},{\overline {a}}\not ={\overline {0}})}$

über dem Körper ${\displaystyle \mathbb {F} _{p}}$ (mit ${\displaystyle p>2}$) studiert werden. Das quadratische Reziprozitätsgesetz kann dabei helfen, schnell zu entscheiden, ob Lösbarkeit vorliegt, oder nicht. Dabei muss der Fall Charakteristik 2 (insbesondere ${\displaystyle \mathbb {F} _{2}}$) gesondert betrachtet werden, da in der Mitternachtsformel durch ${\displaystyle 2a}$, also in solchen Körpern durch ${\displaystyle 0}$ dividiert wird, was nicht erlaubt ist. Daher ist die Theorie quadratischer Gleichungen in solchen Körpern anders.^{[Anm. 9]}

Quadratische Reste und das Legendre-Symbol

Um zu entscheiden, ob eine quadratische Gleichung ${\displaystyle ax^{2}+bx+c=0}$ mit ${\displaystyle a,b,c\in \mathbb {F} _{p}}$ über ${\displaystyle \mathbb {F} _{p}}$ mit einer Primzahl ${\displaystyle p>2}$ lösbar ist, reicht es aus, zu entscheiden, ob die Diskriminante ${\displaystyle b^{2}-4ac}$ ein Quadrat in ${\displaystyle \mathbb {F} _{p}}$ ist. Der Fall ${\displaystyle p=2}$ spielt eine Sonderrolle, da in der Mitternachtsformel durch ${\displaystyle 2a}$ geteilt wird, womit man im Fall ${\displaystyle p=2}$ 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 ${\displaystyle \mathbb {F} _{p}}$ gemeint, die ungleich Null sind und durch Quadrieren eines (anderen) Elements aus ${\displaystyle \mathbb {F} _{p}}$ entstehen. Mit anderen Worten, eine zu ${\displaystyle p}$ teilerfremde Zahl ${\displaystyle n}$ ist genau dann quadratischer Rest modulo ${\displaystyle p}$, falls eine Quadratzahl ${\displaystyle m^{2}}$ existiert, sodass ${\displaystyle n-m^{2}}$ durch ${\displaystyle p}$ teilbar ist. Aus quadratischen Resten kann im betroffenen Körper eine Quadratwurzel gezogen werden, was bei der Auflösung quadratischer Gleichungen von Bedeutung ist. Elemente aus ${\displaystyle \mathbb {F} _{p}}$, die nicht Null und keine quadratischen Reste sind, bezeichnet man auch als quadratische Nichtreste.

Ist zum Beispiel ${\displaystyle p=11}$, so bekommt man durch Quadrieren der Restklassen ${\displaystyle \left\{{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {10}}\right\}}$ modulo ${\displaystyle 11}$:^[8]

${\displaystyle {\overline {1^{2}}}={\overline {1}},\quad {\overline {2^{2}}}={\overline {4}},\quad {\overline {3^{2}}}={\overline {9}},\quad {\overline {4^{2}}}={\overline {16}}={\overline {5}},\quad {\overline {5^{2}}}={\overline {25}}={\overline {3}},\quad {\overline {6^{2}}}={\overline {36}}={\overline {3}},\quad {\overline {7^{2}}}={\overline {49}}={\overline {5}},\quad {\overline {8^{2}}}={\overline {64}}={\overline {9}},\quad {\overline {9^{2}}}={\overline {81}}={\overline {4}},\quad {\overline {10^{2}}}={\overline {100}}={\overline {1}}.}$

Es sind also die Elemente ${\displaystyle {\overline {1}},{\overline {3}},{\overline {4}},{\overline {5}}}$ und ${\displaystyle {\overline {9}}}$ die quadratischen Reste modulo ${\displaystyle 11}$. Somit ist zum Beispiel die Gleichung

${\displaystyle Q_{1}\colon \qquad x^{2}+{\overline {4}}x+{\overline {5}}={\overline {0}}}$

nicht in ${\displaystyle \mathbb {F} _{11}}$ lösbar, denn

${\displaystyle D_{Q_{1}}={\overline {4}}^{2}-{\overline {4}}\cdot {\overline {5}}={\overline {-4}}={\overline {7}}}$

ist quadratischer Nichtrest modulo ${\displaystyle 11}$, und folglich kann in der Mitternachtsformel über ${\displaystyle \mathbb {F} _{11}}$ keine Quadratwurzel aus der Diskriminante gezogen werden. Im Gegensatz dazu ist

${\displaystyle Q_{2}\colon \qquad x^{2}-x+{\overline {2}}=0}$

in ${\displaystyle \mathbb {F} _{11}}$ lösbar, denn es ist

${\displaystyle D_{Q_{2}}={\overline {-1}}^{2}-{\overline {4}}\cdot {\overline {2}}={\overline {-7}}={\overline {4}}}$

quadratischer Rest modulo ${\displaystyle 11}$. In der Tat ist etwa ${\displaystyle x={\overline {5}}}$ eine Lösung, denn ${\displaystyle {\overline {5}}^{2}-{\overline {5}}+{\overline {2}}={\overline {22}}={\overline {0}}}$ modulo ${\displaystyle 11}$.

Bemerkenswerterweise spaltet sich die Menge der quadratischen Reste und Nichtreste in genau zwei gleich große Mengen mit der Anzahl der Elemente ${\displaystyle {\tfrac {p-1}{2}}}$, wenn die Primzahl ${\displaystyle p}$ ungerade ist.^[9] Wie oben gesehen im Fall ${\displaystyle p=11}$, sind es die Mengen ${\displaystyle \{{\overline {1}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {9}}\}}$ und ${\displaystyle \{{\overline {2}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {10}}\}}$ mit je fünf Elementen. Allgemein lassen sich die quadratischen Reste modulo ${\displaystyle p>2}$, wie oben, durch Betrachtung der Elemente

${\displaystyle {\overline {1^{2}}},\quad {\overline {2^{2}}},\quad {\overline {3^{2}}},\quad \cdots ,\quad {\overline {\left({\frac {p-1}{2}}\right)^{2}}}}$

vollständig bestimmen.^{[8][Anm. 10]} Weitere Reste lassen sich folgender Tabelle entnehmen, die für alle Primzahlen bis ${\displaystyle 50}$ vollständig ist:

Verlässt man die modulare Arithmetik und geht wieder zu den ganzen Zahlen über, so ist ${\displaystyle a\in \mathbb {Z} }$ genau dann quadratischer Rest modulo einer Primzahl ${\displaystyle p}$, falls eine Quadratzahl ${\displaystyle m^{2}}$ existiert, sodass ${\displaystyle m^{2}-a}$ durch ${\displaystyle p}$ teilbar ist.^{[Anm. 11]}

Aus mathematischer Sicht ist es sinnvoll, die quadratischen Reste von den Nichtresten zu „trennen“. Dabei wird der ${\displaystyle {\overline {0}}}$ eine besondere Rolle zugeordnet. Zu diesem Zweck definiert man das Legendre-Symbol, benannt nach Adrien-Marie Legendre. Dieses ist eine mathematische Funktion ${\displaystyle \mathbb {F} _{p}\to \{-1,0,1\}}$ mit Definitionsbereich ${\displaystyle \mathbb {F} _{p}}$ und Zielmenge ${\displaystyle \{-1,0,1\}}$, die einem quadratischen Rest den Wert ${\displaystyle 1}$ („positiv“), einem Nichtrest ${\displaystyle -1}$ („negativ“) und der ${\displaystyle {\overline {0}}}$ den Wert ${\displaystyle 0}$ zuordnet. In Symbolen setzt man:^[9]

${\displaystyle \left({\frac {\overline {n}}{p}}\right):=\left({\frac {n}{p}}\right):={\begin{cases}1&\qquad {\text{für }}\mathrm {ggT} (p,n)=1{\text{ und }}n\equiv m^{2}{\bmod {p}}{\text{ für ein }}m\in \mathbb {Z} ,\\-1&\qquad {\text{für }}\mathrm {ggT} (p,n)=1{\text{ und }}n\not \equiv m^{2}{\bmod {p}}{\text{ für alle }}m\in \mathbb {Z} ,\\0&\qquad {\text{für }}p|n.\end{cases}}}$

Hierbei bedeutet ${\displaystyle \mathrm {ggT} }$ den größten gemeinsamen Teiler. Es ist ${\displaystyle ({\tfrac {n}{p}})}$ nicht als Bruch zu verstehen. In der Literatur wird deshalb gelegentlich auch die Notation ${\displaystyle (n|p)}$ genutzt, um Verwechslungen zu vermeiden.^[8] 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, ${\displaystyle p}$-periodisch ist. Es ist dann ${\displaystyle ({\tfrac {\overline {n}}{p}})=({\tfrac {n}{p}}),}$ und letzterer Ausdruck wird am häufigsten verwendet.

Es 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 ${\displaystyle +1}$ und ${\displaystyle -1}$ übergegangen werden. Analog werden in dieser Sichtweise die Regeln ${\displaystyle 1\cdot 1=1}$, ${\displaystyle 1\cdot (-1)=(-1)\cdot 1=-1}$ und ${\displaystyle (-1)\cdot (-1)=1}$ respektiert. Das Legendre-Symbol dient nun als ein „Übersetzer“ zum Beispiel der Regel „Nichtrest mal Nichtrest gleich Rest“ in „negativ mal negativ gleich positiv“.^{[Anm. 12]} Insbesondere folgt, dass das Legendre-Symbol vollständig multiplikativ ist, es gilt also für alle ${\displaystyle a,b\in \mathbb {Z} }$ die Rechenregel^[10]

${\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).}$

Aussage des quadratischen Reziprozitätsgesetzes

Im Folgenden bezeichnet ${\displaystyle \left({\tfrac {a}{p}}\right)}$ mit einer ganzen Zahl ${\displaystyle a}$ und einer Primzahl ${\displaystyle p}$ das Legendre-Symbol. Das quadratische Reziprozitätsgesetz gibt für zwei verschiedene ungerade Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$ eine einfache Formel, die beiden Größen ${\displaystyle ({\tfrac {p}{q}})}$ und ${\displaystyle ({\tfrac {q}{p}})}$ ineinander umzurechnen. Damit kann die Frage, ob ${\displaystyle p}$ ein quadratischer Rest modulo ${\displaystyle q}$ ist, durch Beantwortung der „reziproken“ Frage, ob ${\displaystyle q}$ ein quadratischer Rest modulo ${\displaystyle p}$ ist, ggf. schnell beantwortet werden.

Das quadratische Reziprozitätsgesetz besagt, dass für zwei verschiedene ungerade Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$ gilt:[11]
${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}\quad {\overset {(*)}{=}}\quad {\begin{cases}1&\qquad p\equiv 1{\pmod {4}}\ {\text{oder}}\ q\equiv 1{\pmod {4}},\\-1&\qquad p\equiv 3{\pmod {4}}\ {\text{und}}\ q\equiv 3{\pmod {4}}.\end{cases}}}$
Erklärung zu ${\displaystyle (*)}$: Der Faktor ${\displaystyle {\tfrac {p-1}{2}}}$ ist genau dann eine gerade Zahl, wenn die ungerade Zahl ${\displaystyle p}$ bei Division durch ${\displaystyle 4}$ den Rest ${\displaystyle 1}$ hat. Zum Beispiel ist ${\displaystyle {\tfrac {5-1}{2}}=2}$ (gerade), aber ${\displaystyle {\tfrac {7-1}{2}}=3}$ (ungerade), und es hat ${\displaystyle 5}$ den Rest ${\displaystyle 1}$ bzw. ${\displaystyle 7}$ den Rest ${\displaystyle 3}$ bei Division durch ${\displaystyle 4}$. Ein Produkt ${\displaystyle mn}$ aus ganzen Zahlen ist schließlich genau dann gerade, wenn mindestens ein Faktor gerade ist, und ${\displaystyle (-1)^{mn}}$ ist demnach genau dann positiv, wenn mindestens einer der Faktoren ${\displaystyle m}$ oder ${\displaystyle n}$ gerade ist.[Anm. 13]

Zudem existieren zwei sog. Ergänzungssätze, die eine direkte Berechnung der Werte ${\displaystyle \left({\tfrac {-1}{p}}\right)}$ bzw. ${\displaystyle \left({\tfrac {2}{p}}\right)}$ für ungerade Primzahlen ${\displaystyle p}$ ermöglichen.

1. Ergänzungssatz: Für jede ungerade Primzahl ${\displaystyle p}$ gilt:[11]
${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&\qquad p\equiv 1{\pmod {4}},\\-1&\qquad p\equiv 3{\pmod {4}}.\end{cases}}}$

2. Ergänzungssatz: Für jede ungerade Primzahl ${\displaystyle p}$ gilt:[11]
${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}\quad {\overset {(**)}{=}}\quad {\begin{cases}1&\qquad p\equiv \pm 1{\pmod {8}},\\-1&\qquad p\equiv \pm 3{\pmod {8}}.\end{cases}}}$
Erklärung zu ${\displaystyle (**)}$: Es gilt nach der dritten binomischen Formel ${\displaystyle p^{2}-1=(p-1)(p+1)}$. Da ${\displaystyle p}$ ungerade ist, ist einer der Faktoren ${\displaystyle p\pm 1}$ durch ${\displaystyle 4}$ teilbar, und der andere durch ${\displaystyle 2}$. Somit ist ${\displaystyle {\tfrac {p^{2}-1}{8}}}$ stets eine ganze Zahl. Mit ${\displaystyle p\equiv \pm 1{\pmod {8}}}$ kann aber erreicht werden, dass der Faktor ${\displaystyle p\mp 1}$ sogar durch ${\displaystyle 8}$ teilbar ist, womit ${\displaystyle {\tfrac {p^{2}-1}{8}}}$ eine gerade Zahl ist. In den Fällen ${\displaystyle p\equiv \pm 3{\pmod {8}}}$ kann dies nicht erreicht werden, und ${\displaystyle {\tfrac {p^{2}-1}{8}}}$ ist ungerade.

Sind ${\displaystyle p}$ und ${\displaystyle q}$ zwei verschiedene ungerade Primzahlen, so gilt folglich:^[12]

${\displaystyle \left({\frac {p}{q}}\right)={\begin{cases}-\left({\frac {q}{p}}\right)&\mathrm {f{\ddot {u}}r} \ p\equiv q\equiv 3{\pmod {4}}\\[0.5em]\left({\frac {q}{p}}\right)&{\text{sonst}}\end{cases}}}$

Denn aus ${\displaystyle \left({\tfrac {p}{q}}\right)\in \{-1,1\}}$ folgt bereits ${\displaystyle \left({\tfrac {p}{q}}\right)^{-1}=\left({\tfrac {p}{q}}\right)}$.

Geschichte

Die ersten Andeutungen des quadratischen Reziprozitätsgesetzes finden sich in den Arbeiten von Pierre de Fermat. Fermats Ergebnisse über die Darstellung ganzer Zahlen als Summe zweier Quadrate führten direkt zu dem Problem der Bestimmung des quadratischen Charakters von ${\displaystyle -1}$, also dem Auffinden von ${\displaystyle \left({\tfrac {-1}{p}}\right).}$ Fermat konnte diejenigen ungeraden Primzahlen charakterisieren, die sich als Summe gewisser Kombinationen aus Quadratzahlen schreiben lassen. So zeigte er^{[Anm. 14]}

${\displaystyle p=x^{2}+y^{2},\quad x,y\in \mathbb {Z} \iff p\equiv 1{\pmod {4}}.}$

Zum Beispiel zeigen die Gleichungen

${\displaystyle 5=1+4,\quad 13=4+9,\quad 17=1+16,\quad 29=4+25,\quad 37=1+36,\quad \ldots }$

die ersten ungeraden Primzahlen, die als Summe zweier Quadrate geschrieben werden können. Es handelt sich dabei genau um die Primzahlen, die bei Division durch ${\displaystyle 4}$ den Rest ${\displaystyle 1}$ besitzen. Fermat untersuchte allgemeiner auch die Darstellung von Primzahlen durch quadratische Formen der Form ${\displaystyle q(x,y)=x^{2}+ny^{2}}$, wobei ${\displaystyle n\in \{\pm 2,\pm 3,-5\}}$. Er behauptete etwa, dass

${\displaystyle p=x^{2}+2y^{2},\quad x,y\in \mathbb {Z} \iff p\equiv 1,3{\pmod {8}}}$

${\displaystyle p=x^{2}+3y^{2},\quad x,y\in \mathbb {Z} \iff p=3,}$ oder ${\displaystyle p\equiv 1{\pmod {3}},}$

deutete mögliche Beweise allerdings nur an.^[13] Wenn ${\displaystyle n\in \{2,3\}}$, kann also gezeigt werden, dass eine Primzahl ${\displaystyle p}$, die ${\displaystyle x^{2}+ny^{2}}$ teilt, dabei aber weder ${\displaystyle x}$ noch ${\displaystyle y}$ teilt, selbst die Form ${\displaystyle p=a^{2}+nb^{2}}$ für ein Paar von ganzen Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ hat. Aus dieser Tatsache kann gefolgert werden, dass ${\displaystyle p}$ genau dann durch die quadratischen Formen ${\displaystyle x^{2}+2y^{2}}$ oder ${\displaystyle x^{2}+3y^{2}}$ dargestellt werden kann, wenn ${\displaystyle -2}$ bzw. ${\displaystyle -3}$ ein quadratischer Rest von ${\displaystyle p}$ ist. Zum Beispiel ist die Primzahl ${\displaystyle p=79}$ von der Form ${\displaystyle x^{2}+3y^{2}}$, denn

${\displaystyle 79=4+75=4+3\cdot 25=2^{2}+3\cdot 5^{2}.}$

In der Tat ist ${\displaystyle -3}$ ein quadratischer Rest modulo ${\displaystyle 79}$, denn es teilt ${\displaystyle 79}$ die Zahl ${\displaystyle 32^{2}+3=1\,027=13\cdot 79}$. Aus diesem Grund waren auch die expliziten Ausdrücke ${\displaystyle \left({\tfrac {-2}{p}}\right)}$ und ${\displaystyle \left({\tfrac {-3}{p}}\right)}$ schon bei Fermat von Bedeutung.^[14]

Erstmals entdeckt wurde das quadratische Reziprozitätsgesetz von Leonhard Euler, der es durch empirische Nachforschungen als richtig befand, jedoch keinen Beweis vorlegen konnte. Leopold Kronecker hat darauf verwiesen, dass es unter anderem schnell aus einer Vermutung Eulers aus dessen Schrift Theoremata circa divisores numerorum in hac forma ${\displaystyle pa^{2}\pm qb^{2}}$ contentorum (1744–1746) folgt.^[15] Anschließend widmete Euler sich über zwei Jahrzehnte anderen Themen. Erst die Forschungen von Joseph-Louis Lagrange in den Jahren 1773 bis 1775, insbesondere seine Arbeiten zu einer allgemeinen Theorie der binären quadratischen Formen, bewegten Euler schließlich dazu, sich wieder mit dem Studium der quadratischen Reste detailliert zu befassen. Lagrange wollte die Forschung zu den von Fermat und Euler angestoßenen mathematischen Ideen weiter vorantreiben. Durch explizite Bestimmung von ${\displaystyle \left({\tfrac {\pm 2}{p}}\right)}$, ${\displaystyle \left({\tfrac {\pm 3}{p}}\right)}$ und ${\displaystyle \left({\tfrac {\pm 5}{p}}\right)}$ für ungerade Primzahlen ${\displaystyle p}$, konnte er die Primzahlen mit Darstellung ${\displaystyle x^{2}+5y^{2}}$ sowie ${\displaystyle 2x^{2}+2xy+3y^{2}}$ charakterisieren.^[16] Zum Schluss seiner Ausführungen fasste Lagrange dann alles zusammen, was er über quadratische Reziprozität sagen konnte. Er formulierte seine Resultate stets in Termen des sog. Euler-Kriteriums

${\displaystyle a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}\qquad (\mathrm {ggT} (a,p)=1),}$

das eine Verallgemeinerung des kleinen Satzes von Fermat darstellt. Er hielt fest, dass für eine Primzahl ${\displaystyle p}$ von der Form ${\displaystyle 8n\pm 1}$ der Wert ${\displaystyle 2^{\frac {p-1}{2}}-1}$ bereits durch ${\displaystyle p}$ teilbar und für solche der Form ${\displaystyle 8n\pm 3}$ entsprechend ${\displaystyle 2^{\frac {p-1}{2}}+1}$ durch ${\displaystyle p}$ teilbar ist.^[17] Lagrange gilt damit als Entdecker des 2. Ergänzungssatzes.^[18] In seinem Paper Observationes circa divisionem quadratorum per numeros primos, das 1783 posthum veröffentlicht wurde, gab Euler schließlich eine Formulierung des quadratischen Reziprozitätsgesetzes, die der heute am häufigsten verwendeten sehr nahe kommt. In moderner Notation lautete sie:

Es sei ${\displaystyle p}$ eine ungerade Primzahl und ${\displaystyle a}$ eine ganze Zahl, die nicht durch ${\displaystyle p}$ teilbar ist. Wenn ${\displaystyle q}$ eine Primzahl ist, sodass ${\displaystyle p\equiv \pm q{\pmod {4a}}}$, so gilt ${\displaystyle \left({\tfrac {a}{p}}\right)=\left({\tfrac {a}{q}}\right)}$.

Dies besagt, dass der Wert ${\displaystyle \left({\tfrac {a}{p}}\right)}$ des Legendre-Symbols nur von der Restklasse ${\displaystyle p}$ modulo ${\displaystyle 4a}$ abhängt, und dass der Wert für alle Primzahlen gleich ist, die bei Division durch ${\displaystyle 4a}$ denselben Rest ${\displaystyle r}$ bzw. ${\displaystyle 4a-r}$ haben.^[14] Es konnte elementar gezeigt werden, dass diese von Euler formulierte Version äquivalent zum quadratischen Reziprozitätsgesetz ist.^[19]

Noch im selben Jahrhundert wurde das quadratische Reziprozitätsgesetz von Adrien-Marie Legendre wiederentdeckt^[20] und 1785 in seiner Arbeit Recherches d’Analyse Indéterminée veröffentlicht. Legendre konnte es mit Hilfe seines in dieser Arbeit publizierten Beweises des Satzes von Legendre in Spezialfällen zeigen. Sein Satz befasst sich mit hinreichenden und notwendigen Bedingungen für die Existenz von ganzzahligen Lösungen ${\displaystyle (x,y,z)\not =(0,0,0)}$ einer Gleichung

${\displaystyle ax^{2}+by^{2}+cz^{2}=0\qquad (a,b,c\in \mathbb {Z} ).}$

Er konnte unter Betrachtung der speziellen Gleichung

${\displaystyle x^{2}+py^{2}-qz^{2}=0}$