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.

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}&\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}&\end{matrix}\right.
Inhaltsverzeichnis
1 Rechenregeln
2 Beispiele
3 Effiziente Berechnung des Legendre-Symbols
4 Literatur

Rechenregeln

\left(\frac{p}{q}\right)=\left\{\begin{matrix}-\left(\frac{q}{p}\right)&\mbox{wenn}&p\equiv q\equiv3 \pmod 4\\\left(\frac{q}{p}\right)&\mbox{sonst}\end{matrix}\right.

Beispiele

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

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.

Literatur

See also: Quadratisches Reziprozitätsgesetz, Algorithmus, Euklidischer Algorithmus, Faktor (Mathematik), Jacobi-Symbol, Legendre-Symbol, Multiplikativität, Primfaktorzerlegung, Primzahl, Zähler