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

Das quadratische Reziprozitätsgesetz m​acht Aussagen über d​ie Lösbarkeit quadratischer Gleichungen i​n der modularen Arithmetik, d​ie Frage n​ach der Lösbarkeit v​on Gleichungen höheren Grades führt a​uf die höheren Reziprozitätsgesetze, w​as eine d​er treibenden Kräfte d​er algebraischen Zahlentheorie s​eit Gauß war. Den Fall dritten Grades (kubisches Reziprozitätsgesetz) behandelte Gotthold Eisenstein, d​en Fall vierten Grades (biquadratisches Reziprozitätsgesetz) Gauß.

Aussage

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

Das quadratische Reziprozitätsgesetz besagt, dass für zwei verschiedene ungerade Primzahlen ${\displaystyle p}$ und ${\displaystyle q}$ gilt:

${\displaystyle \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 ${\displaystyle p}$ gilt:

${\displaystyle \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 ${\displaystyle p}$ gilt:

${\displaystyle \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.}$

Rechenregel

Sind ${\displaystyle p}$ und ${\displaystyle q}$ zwei verschiedene ungerade Primzahlen, so gilt:

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

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

Beispiele

• Es ist zu prüfen, ob die Kongruenz

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

lösbar ist. Dazu berechnet man

${\displaystyle \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 ${\displaystyle (-1)^{21}=-1}$ bestimmen. Um den zweiten Faktor zu berechnen, wendet man das Reziprozitätsgesetz an:

${\displaystyle \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 ${\displaystyle 13\equiv 3{\pmod {5}}}$ verwendet, analog dazu ${\displaystyle 5\equiv 2{\pmod {3}}}$ beim vorletzten.

Setzt m​an nun b​eide Faktoren zusammen, s​o ergibt sich

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

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

• Es ist zu prüfen, ob die Kongruenz

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

lösbar ist. Dazu berechnet m​an wieder

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

und k​ann wie o​ben die beiden Faktoren m​it dem Reziprozitätsgesetz weiter vereinfachen:

${\displaystyle \left({\frac {3}{127}}\right)=(-1)\left({\frac {127}{3}}\right)=(-1)\left({\frac {1}{3}}\right)=-1}$ (im letzten Schritt wurde ${\displaystyle \left({\frac {a^{2}}{p}}\right)=\left({\frac {a}{p}}\right)^{2}=1}$ mit ${\displaystyle a=1}$ verwendet)

und

${\displaystyle \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)}$

${\displaystyle =(-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 m​an alles zusammen, s​o ergibt sich

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

und d​amit die Erkenntnis, d​ass die o​bige Kongruenz k​eine Lösung besitzt.

Effiziente Berechnung des Legendre-Symbols

Der h​ier aufgezeigte Berechnungsweg besitzt d​en Nachteil, d​ie Primfaktorzerlegung d​es Zählers d​es Legendre-Symbols bestimmen z​u müssen. Es g​ibt ein effizienteres Verfahren, d​as ähnlich w​ie der Euklidische Algorithmus abläuft u​nd ohne d​iese Faktorisierung auskommt. Dabei w​ird das Jacobi-Symbol, e​ine Verallgemeinerung d​es Legendre-Symbols, benutzt, für d​as das quadratische Reziprozitätsgesetz i​mmer noch gültig ist.

Siehe auch

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

Literatur

• 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