Quadratisches Reziprozitätsgesetz

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 ein quadratischer Rest oder ein quadratischer Nichtrest 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 der wahre Grund des Reziprozitätsgesetzes in der Primfaktorzerlegung im Körper  \mathbb{Q}(\zeta) der n-ten Einheitswurzeln verborgen.

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&\mbox{wenn}&p\equiv q\equiv3 \pmod 4\\1&\mbox{sonst}&\end{matrix}\right.

1. Ergänzungssatz: Für eine ungerade Primzahl p gilt:

\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=\left\{\begin{matrix}1&\mbox{falls}&p\equiv 1\pmod 4\\-1&\mbox{sonst}&\mbox{(also }p\equiv-1\pmod4\mbox{)}&\end{matrix}\right.

2. Ergänzungssatz: Für eine ungerade Primzahl p gilt:

\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\left\{\begin{matrix}1&\mbox{falls}&p\equiv \pm1\pmod 8\\-1&\mbox{sonst}&\mbox{(also }p\equiv\pm3\pmod8\mbox{)}&\end{matrix}\right.

Inhaltsverzeichnis

Rechenregeln

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

\Big(\frac{p}{q}\Big)=\begin{cases}-\big(\frac{q}{p}\big)&\mathrm{wenn}\ p\equiv q\equiv3 \pmod 4\\[,5em]\big(\frac{q}{p}\big)&\mbox{sonst}\end{cases}

Da \Big(\frac{p}{q}\Big)\in\{\pm1\} folgt nämlich \Big(\frac{p}{q}\Big)^{-1}=\Big(\frac{p}{q}\Big)

Beispiele

  • Man möchte entscheiden, ob die Gleichung
x^2\equiv10\pmod{13}

eine Lösung besitzt. Dazu berechnet man

\left(\frac{10}{13}\right)=\left(\frac{2}{13}\right)\left(\frac{5}{13}\right) (das Legendre-Symbol ist multiplikativ im Zähler)

Der erste Faktor lässt sich mit Hilfe des zweiten Ergänzungssatzes zu -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{3}{5}\right) =\left(\frac{5}{3}\right) =\left(\frac{2}{3}\right) =-1

Hier wurde beim zweiten Gleichheitszeichen ausgenutzt, dass 13\equiv3\pmod{5}. Analog auch beim vorletzten Gleichheitszeichen.

Setzt man nun beide Faktoren zusammen, so ergibt sich

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

und damit weiß man, dass die obige Gleichung eine Lösung besitzt. (Die beiden Lösungen lauten 6 und 7.)

  • Man möchte entscheiden, ob die Gleichung
x^2\equiv57\pmod{127}

eine Lösung besitzt. 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

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

und damit die Erkenntnis, dass die obige Gleichung 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 Euklidsche Algorithmus abläuft und ohne Primfaktorisierung auskommt. Dabei wird das Jacobi-Symbol, eine Verallgemeinerung des Legendre-Symbols, benutzt, für das das quadratische Reziprozitätsgesetz immer noch gültig ist.

Weblinks

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

Literatur


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • quadratisches Reziprozitätsgesetz — quadratisches Reziprozitätsgesetz,   Satz der Zahlentheorie. Sind p und q Primzahlen größer als 2, so gilt:   (die Klammern sind legendresche Symbole). Den ersten korrekten Beweis des quadratischen Reziprozitätsgesetzes lieferte 1801 C. F. Gauss …   Universal-Lexikon

  • Reziprozitätsgesetz — Re|zi|pro|zi|täts|ge|setz [lat. reciprocare = hin u. zurückfließen, vorwärts u. rückwärts wenden]: svw. ↑ Bunsen Roscoe Gesetz. * * * Reziprozitätsgesetz,   Mathematik: quadratisches Reziprozitätsgesetz …   Universal-Lexikon

  • Elementare Zahlentheorie — Ursprünglich ist die Zahlentheorie (auch: Arithmetik) ein Teilgebiet der Mathematik, das sich allgemein mit den Eigenschaften der ganzen Zahlen und insbesondere mit den Lösungen von Gleichungen in den ganzen Zahlen (Diophantische Gleichung)… …   Deutsch Wikipedia

  • Hilberts Liste von 23 mathematischen Problemen — Die hilbertschen Probleme sind eine Liste von 23, zum Zeitpunkt der Veröffentlichung, ungelösten Problemem der Mathematik. Sie wurden vom deutschen Mathematiker David Hilbert im Jahr 1900 beim Internationalen Mathematiker Kongress in Paris… …   Deutsch Wikipedia

  • Liste von 23 mathematischen Problemen — Die hilbertschen Probleme sind eine Liste von 23, zum Zeitpunkt der Veröffentlichung, ungelösten Problemem der Mathematik. Sie wurden vom deutschen Mathematiker David Hilbert im Jahr 1900 beim Internationalen Mathematiker Kongress in Paris… …   Deutsch Wikipedia

  • Prinzip der Gegenseitigkeit — Reziprozität (lat. reciprocus, „aufeinander bezüglich“, „wechselseitig“), adj. reziprok steht für: den Kehrwert eines Bruches in der Mathematik, und entsprechend die Antiproportionalität einer Funktion Quadratisches Reziprozitätsgesetz in der… …   Deutsch Wikipedia

  • Reziprok — Reziprozität (lat. reciprocus, „aufeinander bezüglich“, „wechselseitig“), adj. reziprok steht für: den Kehrwert eines Bruches in der Mathematik, und entsprechend die Antiproportionalität einer Funktion Quadratisches Reziprozitätsgesetz in der… …   Deutsch Wikipedia

  • Disquisitiones arithmeticae — Titelseite der Erstausgabe Die Disquisitiones Arithmeticae (lateinisch für Zahlentheoretische Untersuchungen) sind ein Lehrbuch der Zahlentheorie („Höhere Arithmetik“ in Gauß’ Worten), das der deutsche Mathematiker Carl Friedrich Gauß 1798 mit… …   Deutsch Wikipedia

  • Quadratische-Reste-Problem — Der quadratische Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl a ist ein quadratischer Rest bezüglich eines Moduls m, wenn sie zu m teilerfremd ist und es eine Zahl x gibt, für die die Kongruenz gilt. Für den… …   Deutsch Wikipedia

  • Quadratischer Nichtrest — Der quadratische Rest ist ein Begriff aus dem mathematischen Teilgebiet Zahlentheorie. Eine Zahl a ist ein quadratischer Rest bezüglich eines Moduls m, wenn sie zu m teilerfremd ist und es eine Zahl x gibt, für die die Kongruenz gilt. Für den… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”