Quadratisches Reziprozitätsgesetz - LinkFang.de





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

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ß.

Aussage

Das quadratische Reziprozitätsgesetz besagt, dass für zwei verschiedene ungerade Primzahlen [math]p[/math] und [math]q[/math] gilt:

[math]\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\equiv3 \pmod 4\\1&\mbox{sonst}&\mbox{(also }\mathrm{f\ddot{u}r}\ p\equiv1\pmod4\quad \mbox{oder}\quad q\equiv1\pmod4\mbox{)}&\end{matrix}\right.[/math]

1. Ergänzungssatz: Für jede ungerade Primzahl [math]p[/math] gilt:

[math]\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\pmod4\mbox{)}&\end{matrix}\right.[/math]

2. Ergänzungssatz: Für jede ungerade Primzahl [math]p[/math] gilt:

[math]\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\left\{\begin{matrix}1&\mathrm{f\ddot{u}r}&p\equiv \pm1\pmod 8\\-1&\mbox{sonst}&\mbox{(also }\mathrm{f\ddot{u}r}\ p\equiv\pm3\pmod8\mbox{)}&\end{matrix}\right.[/math]

Rechenregel

Sind [math]p[/math] und [math]q[/math] zwei verschiedene ungerade Primzahlen, so gilt:

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

Aus [math]\left(\frac{p}{q}\right)\in\{\pm1\}[/math] folgt nämlich [math]\left(\frac{p}{q}\right)^{-1}=\left(\frac{p}{q}\right)[/math].

Beispiele

[math]x^2\equiv10\pmod{13}[/math]

lösbar ist. Dazu berechnet man

[math]\left(\frac{10}{13}\right)=\left(\frac{2}{13}\right)\left(\frac{5}{13}\right)[/math] (das Legendre-Symbol ist multiplikativ im oberen Argument).

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

[math]\left(\frac{5}{13}\right)=\left(\frac{13}{5}\right) =\left(\frac{3}{5}\right) =\left(\frac{5}{3}\right) =\left(\frac{2}{3}\right) =-1[/math]

Hier wurde beim zweiten Gleichheitszeichen [math]13\equiv3\pmod{5}[/math] verwendet, analog dazu [math]5\equiv2\pmod{3}[/math] beim vorletzten.

Setzt man nun beide Faktoren zusammen, so ergibt sich

[math]\left(\frac{10}{13}\right)=(-1)(-1)=1[/math]

und damit weiß man, dass die obige Kongruenz eine Lösung besitzt. Modulo 13 gibt es sogar zwei Lösungen, nämlich [math]x\equiv\pm6\pmod{13}[/math].

  • Es ist zu prüfen, ob die Kongruenz
[math]x^2\equiv57\pmod{127}[/math]

lösbar ist. Dazu berechnet man wieder

[math]\left(\frac{57}{127}\right)=\left(\frac{3}{127}\right)\left(\frac{19}{127}\right)[/math]

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

[math]\left(\frac{3}{127}\right) =(-1)\left(\frac{127}{3}\right) =(-1)\left(\frac{1}{3}\right) =-1[/math] (im letzten Schritt wurde [math]\left(\frac{a^2}{p}\right)=\left(\frac{a}{p}\right)^2=1[/math] mit [math]a=1[/math] verwendet)

und

[math]\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)[/math]
[math]=(-1)\left(\frac{2}{13}\right)\left(\frac{3}{13}\right) =(-1)(-1)\left(\frac{13}{3}\right) =(-1)(-1)\left(\frac{1}{3}\right) =1[/math]

Setzt man alles zusammen, so ergibt sich

[math]\left(\frac{57}{127}\right)=(-1)\cdot 1=-1[/math]

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

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

Weblinks

 Wikiversity: Ein Beweis des quadratischen Reziprozitätgesetzes – Kursmaterialien, Forschungsprojekte und wissenschaftlicher Austausch

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Quadratisches Reziprozitätsgesetz (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.