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 unterschiedliche Primzahlen p und q gilt:
1. Ergänzungssatz: Für eine ungerade Primzahl p gilt:
2. Ergänzungssatz: Für eine ungerade Primzahl p gilt:
Beispiele
- Man möchte entscheiden, ob die Gleichung
eine Lösung besitzt. Dazu berechnet man
- (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:
-
Hier wurde beim zweiten Gleichheitszeichen ausgenutzt, dass . Analog auch beim vorletzten Gleichheitszeichen.
Setzt man nun beide Faktoren zusammen, so ergibt sich,
-
und damit weiss man, dass die obige Gleichung eine Lösung besitzt. (Die beiden Lösungen lauten 6 und 7.)
- Man möchte entscheiden, ob die Gleichung
eine Lösung besitzt. Dazu berechnet man wieder
-
und kann wie oben die beiden Faktoren mit dem Reziprozitätsgesetz weiter vereinfachen:
-
und
-
Setzt man alles zusammen, so ergibt sich
-
und damit die Erkenntnis, dass die obige Gleichung keine Lösung besitzt.
