Benutzer:Googolplexian1221/Quadratisches Reziprozitätsgesetz

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 $\mathbb {Q} (\zeta )$ mit einer primitiven Einheitswurzel $\zeta$ . Gauß selbst hat mehrere methodisch verschiedene Beweise vorgelegt.

Das quadratische Reziprozitätsgesetz stellt für zwei ungerade, ungleiche Primzahlen $p$ und $q$ einen Zusammenhang zwischen den Fragen her, ob eine Quadratzahl $m^{2}$ existiert, sodass $p$ die Zahl $q-m^{2}$ teilt, und umgekehrt eine Quadratzahl $n^{2}$ existiert, sodass $q$ die Zahl $p-n^{2}$ teilt. Das Wort „Reziprozität“ bezieht sich darauf, dass die Rollen von $p$ und $q$ 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

Endliche Körper

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 $0$ (neutrales Element der Addition) und $1$ (neutrales Element der Multiplikation) Teil eines Körpers sein. Ferner soll durch jede Zahl ungleich der $0$ dividiert werden können. Wichtige Beispiele sind der Körper der reellen Zahlen (Bezeichnung: $\mathbb {R}$ ) oder der Körper der rationalen Zahlen (Bezeichnung: $\mathbb {Q}$ ).

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 $2$ ein Element von $\mathbb {Q}$ , kurz $2\in \mathbb {Q}$ , aber ${\sqrt {2}}$ ist eine irrationale Zahl, also ${\sqrt {2}}\notin \mathbb {Q}$ . Ähnlich besitzt $-1$ 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 $\mathbb {Q}$ hinzunehmen, und größere Körper konstruieren. Ein Beispiel ist der Körper $\mathbb {Q} ({\sqrt {2}})$ , der aus allen Zahlen $x+{\sqrt {2}}y$ mit $x,y\in \mathbb {Q}$ besteht (siehe auch: Zahlkörper, und zum Beispiel Quadratischer Zahlkörper). Dies ist, zusammen mit $\mathbb {Q}$ und $\mathbb {R}$ , ein weiteres Beispiel für einen Körper mit unendlich vielen Elementen. Bemerkenswert ist es aber, dass auch Körper $\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

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 $\mathbb {K}$ nur endlich viele Elemente hat. Da man stets $0\not =1$ hat (sonst wäre $\mathbb {K} =\{0\}$ , und diesen trivialen Fall schließt man aus), gibt es damit eine kleinste natürliche Zahl $p$ , so dass

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

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

\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}}\}=\{0+5\mathbb {Z} ,1+5\mathbb {Z} ,2+5\mathbb {Z} ,3+5\mathbb {Z} ,4+5\mathbb {Z} \},

mit

\mathbb {Z} =

Menge der ganzen Zahlen.

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

4+5\mathbb {Z} =\{\ldots ,-6,-1,4,9,14,19,\ldots \}.

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

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

Die jeweiligen Repräsentanten ergeben bei Division durch $5$ alle den selben Rest $4$ , und gehören so zur selben Restklasse. Man sieht damit, dass Vielfache von $5$ 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 $\mathbb {Z}$ : Zum Beispiel ist

{\overline {4}}+{\overline {4}}={\overline {8}}={\overline {3}}

{\overline {1}}-{\overline {4}}={\overline {-3}}={\overline {2}}

{\overline {2}}\cdot {\overline {3}}={\overline {6}}={\overline {1}}

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 $5$ teilbar ist, liegt dies auf der Hand: Zum Beispiel ist

{\overline {4}}+{\overline {2}}={\overline {6}}={\overline {1}}

aber auch

{\overline {19}}+{\overline {-3}}={\overline {16}}={\overline {1}}.

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

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

ab=1

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

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

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

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

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

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 $N$ , den „Modul“, bezeichnet man zwei ganze Zahlen $a$ und $b$ als kongruent modulo $N$ , falls $N$ deren Differenz teilt, also

N|(a-b).

Man schreibt in diesem Falle die Kongruenz auch als

a\equiv b\mod {N},

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

Quadratische Gleichungen

Eine quadratische Gleichung ist eine Gleichung der Form

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

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

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

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

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

identifiziert, erkennt man, dass die Gleichung $Q$

genau dann zwei verschiedene Lösungen besitzt, falls $b^{2}-4ac\not =0$ ein Quadrat im zugrunde liegenden Körper ist (also der Term ${\sqrt {b^{2}-4ac}}$ im Körper enthalten ist),
genau dann eine (doppelte) Lösungen besitzt, falls $b^{2}-4ac=0$ ,
genau dann keine Lösung besitzt, falls $b^{2}-4ac=0$ kein Quadrat im zugrunde liegenden Körper ist.

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

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

{\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 $\mathbb {F} _{p}$ studiert werden. Das quadratische Reziprozitätsgesetz kann dabei helfen, schnell zu entscheiden, ob Lösbarkeit vorliegt, oder nicht.

Das Legendre-Symbol

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

Ist zum Beispiel $p=7$ , so bekommt man durch Quadrieren der Restklassen $\{{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}}\}$ modulo $7$ :

{\overline {1}},\quad {\overline {4}},\quad {\overline {9}}={\overline {2}},\quad {\overline {16}}={\overline {2}},\quad {\overline {25}}={\overline {4}},\quad {\overline {36}}={\overline {1}}.

Es sind also die Elemente ${\overline {1}},{\overline {2}}$ und ${\overline {4}}$ die quadratischen Reste modulo $7$ . Somit ist zum Beispiel die Gleichung

x^{2}+{\overline {3}}x+{\overline {5}}=0

nicht in $\mathbb {F} _{7}$ lösbar, denn ${\overline {3}}^{2}-{\overline {4}}\cdot {\overline {5}}={\overline {-11}}={\overline {3}}$ ist quadratischer Nichtrest modulo $7$ . Im Gegensatz dazu ist $x^{2}-x+{\overline {1}}=0$ in $\mathbb {F} _{7}$ lösbar, denn es ist ${\overline {-1}}^{2}-{\overline {4}}={\overline {-3}}={\overline {4}}$ ein quadratischer Rest modulo $7$ . In der Tat ist etwa $x={\overline {3}}$ eine Lösung, denn ${\overline {3}}^{2}-{\overline {3}}+{\overline {1}}={\overline {7}}={\overline {0}}$ .

Adrien-Marie Legendre

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

\left({\frac {\overline {n}}{p}}\right):={\begin{cases}1&{\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&{\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&{\text{für }}p|n.\end{cases}}

Es ist $({\tfrac {n}{p}})$ nicht als Bruch zu verstehen. In der Literatur wird deshalb gelegentlich auch die Notation $(n|p)$ 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, $p$ -periodisch ist. Es ist dann $({\tfrac {\overline {n}}{p}})=({\tfrac {n}{p}})$ , 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 ${\tfrac {p-1}{2}}$ , wenn die Primzahl $p$ ungerade ist. Wie oben gesehen im Fall $p=7$ , sind es die Mengen $\{{\overline {1}},{\overline {2}},{\overline {4}}\}$ und $\{{\overline {3}},{\overline {5}},{\overline {6}}\}$ 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 $+1$ und $-1$ übergegangen werden. Analog werden in dieser Sichtweise die Regeln $1\cdot 1=1$ , $1\cdot (-1)=(-1)\cdot 1=-1$ und $(-1)\cdot (-1)=1$ 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

\mathbb {F} _{p}\setminus \{{\overline {0}}\}\longrightarrow \{-1,1\}.

Aussage des quadratischen Reziprozitätsgesetzes

Im Folgenden bezeichnet $\left({\frac {a}{p}}\right)$ mit einer ganzen Zahl $a$ und einer Primzahl $p$ das Legendre-Symbol.

Das quadratische Reziprozitätsgesetz besagt, dass für zwei verschiedene ungerade Primzahlen  $p$  und  $q$  gilt:
 $\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}=\left\{{\begin{matrix}-1&\mathrm {f{\ddot {u}}r} &p\equiv q\equiv 3{\pmod {4}}\\1&{\mbox{sonst}}&{\mbox{(also }}\mathrm {f{\ddot {u}}r} \ p\equiv 1{\pmod {4}}\quad {\mbox{oder}}\quad q\equiv 1{\pmod {4}}{\mbox{)}}&\end{matrix}}\right.$

1. Ergänzungssatz: Für jede ungerade Primzahl  $p$  gilt:
 $\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}=\left\{{\begin{matrix}1&\mathrm {f{\ddot {u}}r} &p\equiv 1{\pmod {4}}\\-1&{\mbox{sonst}}&{\mbox{(also }}\mathrm {f{\ddot {u}}r} \ p\equiv -1{\pmod {4}}{\mbox{)}}&\end{matrix}}\right.$

2. Ergänzungssatz: Für jede ungerade Primzahl  $p$  gilt:
 $\left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}=\left\{{\begin{matrix}1&\mathrm {f{\ddot {u}}r} &p\equiv \pm 1{\pmod {8}}\\-1&{\mbox{sonst}}&{\mbox{(also }}\mathrm {f{\ddot {u}}r} \ p\equiv \pm 3{\pmod {8}}{\mbox{)}}&\end{matrix}}\right.$

Sind $p$ und $q$ zwei verschiedene ungerade Primzahlen, so gilt folglich:

\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}}

Aus $\left({\frac {p}{q}}\right)\in \{-1,1\}$ folgt nämlich $\left({\frac {p}{q}}\right)^{-1}=\left({\frac {p}{q}}\right)$ .

Geschichte

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.

Beispiele

Es ist zu prüfen, ob die Kongruenz

x^{2}\equiv 10{\pmod {13}}

lösbar ist. Dazu berechnet man

\left({\frac {10}{13}}\right)=\left({\frac {2}{13}}\right)\left({\frac {5}{13}}\right)

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

Der erste Faktor lässt sich mit Hilfe des zweiten Ergänzungssatzes zu $(-1)^{21}=-1$ bestimmen. Um den zweiten Faktor zu berechnen, wendet man das Reziprozitätsgesetz an:

\left({\frac {5}{13}}\right)=\left({\frac {13}{5}}\right)=\left({\frac {13-2\cdot 5}{5}}\right)=\left({\frac {3}{5}}\right)=\left({\frac {5}{3}}\right)=\left({\frac {2}{3}}\right)=-1

Hier wurde beim zweiten Gleichheitszeichen $13\equiv 3{\pmod {5}}$ verwendet, analog dazu $5\equiv 2{\pmod {3}}$ beim vorletzten.

Setzt man nun beide Faktoren zusammen, so ergibt sich

\left({\frac {10}{13}}\right)=(-1)(-1)=1.

Damit weiß man, dass die obige Kongruenz eine Lösung besitzt, und wegen $13\mid (36-10)$ gilt tatsächlich $(\pm 6)^{2}\equiv 10{\pmod {13}}$ .

Es ist zu prüfen, ob die Kongruenz

x^{2}\equiv 57{\pmod {127}}

lösbar ist. Dazu berechnet man wieder

\left({\frac {57}{127}}\right)=\left({\frac {3}{127}}\right)\left({\frac {19}{127}}\right)

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

\left({\frac {3}{127}}\right)=(-1)\left({\frac {127}{3}}\right)=(-1)\left({\frac {1}{3}}\right)=-1

(im letzten Schritt wurde

\left({\frac {a^{2}}{p}}\right)=\left({\frac {a}{p}}\right)^{2}=1

mit

a=1

verwendet)

und

\left({\frac {19}{127}}\right)=(-1)\left({\frac {127}{19}}\right)=(-1)\left({\frac {13}{19}}\right)=(-1)\left({\frac {19}{13}}\right)=(-1)\left({\frac {6}{13}}\right)

=(-1)\left({\frac {2}{13}}\right)\left({\frac {3}{13}}\right)=(-1)(-1)^{21}\left({\frac {13}{3}}\right)=(-1)(-1)\left({\frac {1}{3}}\right)=1

Setzt man alles zusammen, so ergibt sich

\left({\frac {57}{127}}\right)=(-1)\cdot 1=-1

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

Beweise

Analoga und Verallgemeinerungen

Kubisches Reziprozitätsgesetz

Biquadratisches Reziprozitätsgesetz

Artinsches Reziprozitätsgesetz

Analogon zu elliptischen Kurven

Effiziente Berechnung des Legendre-Symbols

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.

Siehe auch

Lemma von Zolotareff, eine Beweisvariante für das quadratische Reziprozitätsgesetz mit Hilfe von Permutationen

Literatur

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.

Weblinks

Wikiversity: Ein Beweis des quadratischen Reziprozitätsgesetzes – Kursmaterialien

Kategorie:Zahlentheoretischer Algorithmus Kategorie:Satz (Zahlentheorie)