Quadratisches Reziprozitätsgesetz

Kernidee und mathematische Grundlagen

Das quadratische Reziprozitätsgesetz ist ein grundlegendes Resultat der Zahlentheorie. Es entscheidet, ob eine Zahl a ein quadratischer Rest modulo einer ungeraden Primzahl p ist. Das bedeutet: Es gibt eine ganze Zahl m mit m² ≡ a (mod p), beziehungsweise p teilt m² − a.

Für zwei verschiedene ungerade Primzahlen p und q werden zwei Fragen miteinander verglichen: Ist p ein quadratischer Rest modulo q, und ist q ein quadratischer Rest modulo p? Das Gesetz beschreibt, wie diese beiden Fragen zusammenhängen.

Die zugrunde liegende modulare Arithmetik rechnet mit Restklassen. Zwei ganze Zahlen a und b heißen kongruent modulo N, wenn N | (a − b); man schreibt a ≡ b (mod N). Für eine Primzahl p bilden die Restklassen modulo p den endlichen Körper 𝔽ₚ. In einem Körper sind Addition, Subtraktion, Multiplikation und Division durch jedes von 0 verschiedene Element möglich. Ist der Modul zusammengesetzt, entsteht im Allgemeinen nur ein kommutativer Ring; beispielsweise ist in ℤ/4ℤ keine Division durch 2 möglich.

Eine quadratische Gleichung hat die Form ax² + bx + c = 0 mit a ≠ 0. Ihre Diskriminante ist D = b² − 4ac. Über einem Körper besitzt sie genau dann Lösungen, wenn die Quadratwurzel aus D im betreffenden Körper existiert. Für D ≠ 0 gibt es zwei verschiedene Lösungen, für D = 0 eine doppelte Lösung und wenn D kein Quadrat ist keine Lösung. In 𝔽ₚ mit p > 2 kann diese Frage daher auf die Untersuchung quadratischer Reste zurückgeführt werden. Der Fall p = 2 ist gesondert zu behandeln, weil die Mitternachtsformel durch 2a und damit durch 0 teilen würde.

Quadratische Reste, Legendre-Symbol und Hauptsatz

Ein von 0 verschiedener Rest modulo einer ungeraden Primzahl p heißt quadratischer Rest, wenn er als Quadrat einer Restklasse entsteht. Ein Nichtnull-Element, das kein Quadrat ist, heißt quadratischer Nichtrest. Für ungerade p gibt es genau (p − 1)/2 quadratische Reste und ebenso viele Nichtreste.

Beispiel modulo 11: Die quadratischen Reste sind 1, 3, 4, 5 und 9. Deshalb ist x² + 4x + 5 = 0 in 𝔽₁₁ nicht lösbar, denn die Diskriminante D = 4² − 4 · 5 = −4 ≡ 7 ist ein Nichtrest. Dagegen ist x² − x + 2 = 0 lösbar, weil D = (−1)² − 4 · 2 = −7 ≡ 4 ein Rest ist; x = 5 ist eine Lösung.

Das Legendre-Symbol ordnet einem Element modulo p den Wert 1, −1 oder 0 zu:

• (a/p) = 1, wenn a teilerfremd zu p und quadratischer Rest modulo p ist;
• (a/p) = −1, wenn a teilerfremd zu p und quadratischer Nichtrest ist;
• (a/p) = 0, wenn p | a.

Das Symbol ist kein Bruch. Es ist p-periodisch und vollständig multiplikativ: (ab/p) = (a/p)(b/p). Daher entspricht das Produkt zweier Reste einem Rest, das Produkt aus Rest und Nichtrest einem Nichtrest und das Produkt zweier Nichtreste wieder einem Rest.

Für zwei verschiedene ungerade Primzahlen p und q gilt das quadratische Reziprozitätsgesetz:

(p/q)(q/p) = (−1)^(((p−1)/2)((q−1)/2)).

Äquivalent dazu gilt: Hat p oder q bei Division durch 4 den Rest 1, so sind beide Legendre-Symbole gleich. Haben beide den Rest 3, so sind sie entgegengesetzt. In der ursprünglichen Fragestellung bedeutet das: Im ersten Fall sind die beiden Restfragen entweder beide mit Ja oder beide mit Nein zu beantworten; im zweiten Fall genau eine mit Ja.

Beispiele sind p = 5 und q = 19: Beide Fragen haben eine positive Antwort, etwa 2² − 19 = −15 und 9² − 5 = 76. Bei p = 3 und q = 7 ist 1² − 7 = −6 durch 3 teilbar, aber 3 ist kein quadratischer Rest modulo 7; genau eine Frage ist positiv.

Die Ergänzungssätze erlauben die direkte Berechnung wichtiger Sonderfälle:

• (−1/p) = (−1)^((p−1)/2) = 1 für p ≡ 1 (mod 4) und −1 für p ≡ 3 (mod 4).
• (2/p) = (−1)^((p²−1)/8) = 1 für p ≡ ±1 (mod 8) und −1 für p ≡ ±3 (mod 8).

Berechnung und Anwendungen

Das Gesetz macht schwierige Restfragen durch Vertauschen von Zähler und Nenner oft leichter. Zusammen mit der Multiplikativität, der Periodizität und den Ergänzungssätzen kann es Legendre-Symbole effizient berechnen.

Ein Beispiel ist (219/383). Wegen 219 = 3 · 73 gilt (219/383) = (3/383)(73/383). Mit dem Reziprozitätsgesetz und der Periodizität erhält man (3/383) = 1 sowie (73/383) = (18/73) = (2/73)(3/73)² = 1. Also ist (219/383) = 1; tatsächlich ist 219 ein quadratischer Rest modulo 383, denn 169² − 219 = 2 · 37 · 383.

Für eine quadratische Kongruenz ax² + bx + c ≡ 0 (mod p), p ungerade und ggT(p,a) = 1, ist die Diskriminante D = b² − 4ac entscheidend. Die Anzahl der Lösungen beträgt genau 1 + (D/p). Damit gibt es bei einem Rest zwei Lösungen, bei D ≡ 0 eine Lösung und bei einem Nichtrest keine Lösung. Bei einem beliebigen Modul m kann man nach dem Chinesischen Restsatz auf die Kongruenzen modulo den Primzahlpotenzen in der Zerlegung m = p₁ᶜ¹⋯pᵣᶜʳ zurückführen. Für ungerades m und ggT(D,m) = 1 genügt die Prüfung der Kongruenzen y² ≡ D (mod pⱼ); bei geradem m oder nicht teilerfremder Diskriminante gilt diese Vereinfachung nicht uneingeschränkt.

In der Kryptographie können quadratische Reste für Null-Wissen-Beweise verwendet werden. Beim 1985 von Adi Shamir entwickelten Verfahren wählt Alice große Primzahlen p und q, veröffentlicht n = pq, behält (p,q) aber geheim und besitzt eine Quadratwurzel u eines öffentlichen quadratischen Restes v modulo n. Bob stellt wiederholt Zufallsfragen. Ohne u kann ein Angreifer jede einzelne Frage nur mit ungefähr 50 Prozent Wahrscheinlichkeit richtig beantworten; mit u kann Alice alle Fragen korrekt beantworten. Die Sicherheit beruht darauf, dass die Faktorisierung eines Produkts aus zwei sehr großen Primzahlen als extrem schwer gilt.

Das Gesetz liefert außerdem Aussagen über die Verteilung von Resten und Nichtresten. Für festes a hängt (a/p) nur von der Restklasse von p modulo 4|a| ab. Daraus entstehen quadratische Dirichlet-Charaktere. Jede nichtquadratische ganze Zahl ist für unendlich viele Primzahlen ein Nichtrest; eine Zahl ist genau dann für alle bis auf endlich viele Primzahlen ein Rest, wenn sie eine Quadratzahl ist. Für jede nichtleere endliche Primzahlmenge P und jede Zuordnung ε: P → {−1,1} besitzt die Menge der Primzahlen mit (q/p) = ε(q) für alle q ∈ P die asymptotische Dichte 1/2^|P|. Außerdem gibt es für jede Primzahl q > 3 eine Primzahl 2 < p < 8(√q + 1) mit (q/p) = −1.

Primzahltheorie, Quadratesummen und diophantische Gleichungen

Das quadratische Reziprozitätsgesetz schränkt mögliche Primteiler spezieller Zahlen ein. Die Fermat-Zahlen sind Fₙ = 2^(2ⁿ) + 1. Jeder Primteiler p von Fₙ für n ≥ 2 hat die Form p = 2ⁿ⁺²k + 1. Für F₅ = 4 294 967 297 folgt daher p = 128k + 1; tatsächlich gilt F₅ = 641 · 6 700 417.

Für Mersenne-Zahlen Mₚ = 2ᵖ − 1 mit primem p gilt: Ist q = 2p + 1 ebenfalls prim, so teilt q genau dann Mₚ, wenn q ≡ ±1 (mod 8). Eine Primzahl p mit ebenfalls primem 2p + 1 heißt Sophie-Germain-Primzahl. Für p = 11 ist q = 23 prim und q teilt M₁₁ = 2047 = 23 · 89.

Das Gesetz kann auch in Spezialfällen des Dirichletschen Primzahlsatzes eingesetzt werden. Dieser besagt, dass jede arithmetische Progression mit teilerfremdem Anfangsglied und Abstand unendlich viele Primzahlen enthält. So gibt es unendlich viele Primzahlen p ≡ 1 (mod 4). Ähnliche elementare Argumente lassen sich teilweise für Abstände 3, 4 und 6 führen; der allgemeine Satz benötigt Methoden der komplexen Analysis.

Bei Quadratesummen entscheidet das Gesetz unter anderem, welche ungeraden Primzahlen als Summe zweier Quadrate darstellbar sind. Es gilt:

p = x² + y² mit x,y ∈ ℤ genau dann, wenn p ≡ 1 (mod 4).

Beispiele sind 5 = 1² + 2², 13 = 2² + 3², 17 = 1² + 4² und 41 = 4² + 5². Ähnliche Fragen betreffen Formen wie x² + 3y² oder gemischte quadratische Formen.

Bei diophantischen Gleichungen, also Polynomgleichungen mit ganzzahligen Koeffizienten und gesuchten ganzzahligen Lösungen, kann das Gesetz in manchen Fällen die Unlösbarkeit zeigen. Beispiele sind x³ − y² = 24 und x⁵ − y² = 52. Ein allgemeines Entscheidungsverfahren für beliebige diophantische Gleichungen existiert nicht.

In der arithmetischen Geometrie verbindet das Gesetz Untersuchungen über rationalen Zahlen mit solchen über endlichen Körpern. Der Satz von Hasse-Minkowski besagt für quadratische Formen, dass eine nichttriviale rationale Lösung genau dann existiert, wenn eine reelle Lösung und für jede Primzahl eine Lösung modulo p existieren. Für die Gleichung x² = d hat die Lösungsmengenanzahl über 𝔽ₚ die Form aₚ(Q) + 1 mit aₚ(Q) = (4d/p). Diese Werte hängen nur von der Restklasse von p modulo 4|d| ab und können als Eigenwerte geeigneter linearer Abbildungen verstanden werden. Für elliptische Kurven treten an die Stelle des Legendre-Symbols Modulformen und Hecke-Operatoren; dies steht im Zusammenhang mit dem 1995 bewiesenen Modularitätssatz von Andrew Wiles und Richard Taylor.

Beweisideen und historische Einordnung

Das Gesetz wurde von Euler entdeckt; Legendre formulierte es 1785, sein Beweis war jedoch unvollständig. Carl Friedrich Gauß gab den ersten vollständigen Beweis in den Disquisitiones Arithmeticae von 1801 und hatte bereits 1796 einen Beweis gefunden. Gauß entwickelte mindestens acht methodisch verschiedene Beweise; insgesamt wurden mehr als 300 Beweise veröffentlicht. Die Entwicklung des Gesetzes war ein Ausgangspunkt der modernen algebraischen Zahlentheorie.

Ein zentraler Zugang ist das Lemma von Gauß. Für Hₚ = {1̅, 2̅, …, ((p−1)/2)̅} wird jedes Produkt j·a eindeutig als εⱼ(a)hⱼ(a) mit εⱼ(a) ∈ {−1,1} und hⱼ(a) ∈ Hₚ geschrieben. Dann gilt (a/p) = ∏ⱼ εⱼ(a). Mit dem Euler-Kriterium und einer Darstellung der Vorzeichen durch ganzzahlige Teile kann man das Reziprozitätsgesetz auf ein Zählen von Gitterpunkten in einem durch p und q bestimmten Rechteck zurückführen.

Eisensteins Beweis von 1845 verwendet das Lemma von Gauß und eine trigonometrische Produktidentität für den Sinus. Nach dem Vertauschen von p und q unterscheiden sich die entstehenden Produkte nur durch das Vorzeichen (−1)^(((p−1)/2)((q−1)/2)); genau daraus folgt der Hauptsatz.

Ein analytischer Beweis untersucht die Jacobische Thetafunktion in der Nähe von τ = 0. Zwei verschiedene Grenzwertberechnungen führen zur Landsberg-Schaar-Formel und zu Formeln für quadratische Gauß-Summen. Der Vergleich zweier Berechnungen des Produkts entsprechender Gauß-Summen ergibt das Reziprozitätsgesetz.

Der kombinatorische Beweis nutzt das Lemma von Zolotareff: Die Abbildung πₐ,ₚ(k̅) = a·k̅ permutiert die von 0 verschiedenen Restklassen modulo p, und ihr Permutationsvorzeichen ist gleich dem Legendre-Symbol (a/p). Die Ergänzungssätze können unter anderem direkt mit dem Euler-Kriterium und durch Betrachtung der geraden Zahlen modulo p bewiesen werden.

Verallgemeinerungen und höhere Reziprozität

Das Legendre-Symbol lässt sich zum Jacobi-Symbol für ungerade zusammengesetzte Moduln erweitern. Ist n = p₁^ν¹⋯pₖ^νᵏ, so definiert man (a/n) = (a/p₁)^ν¹⋯(a/pₖ)^νᵏ. Für ungerade m,n > 1 gilt weiterhin (m/n) = (−1)^(((m−1)/2)((n−1)/2))(n/m).

Aus (a/n) = −1 folgt, dass x² ≡ a (mod n) unlösbar ist. Der Wert (a/n) = 1 garantiert bei zusammengesetztem n jedoch nicht, dass eine Lösung existiert.

Höhere Reziprozitätsgesetze behandeln dritte oder vierte Potenzen. Für das kubische Gesetz werden die ganzen Zahlen durch die Eisenstein-Zahlen ℤ[ω] mit ω = e^(2πi/3) = −1/2 + (√3/2)i erweitert. Ihre Norm ist N(a + bω) = a² − ab + b². In diesem Ring werden Primelemente und ein kubisches Legendre-Symbol definiert; für primäre Primelemente π und θ gilt (π/θ)₃ = (θ/π)₃.

Das biquadratische Reziprozitätsgesetz wird analog im Ring ℤ[i] der Gaußschen Zahlen formuliert. Für primäre Primelemente π und θ ≡ 1 (mod 2 + 2i) gilt (θ/π)₄ = (π/θ)₄ (−1)^(((N(θ)−1)(N(π)−1))/16).

Das Artinsche Reziprozitätsgesetz verallgemeinert die bekannten Reziprozitätsgesetze innerhalb der algebraischen Zahlentheorie. Für eine abelsche Erweiterung L/K ordnet das Artin-Symbol geeigneten Primidealen ein Element der Galois-Gruppe Gal(L/K) zu. Das Gesetz beschreibt den Kern dieser Artin-Abbildung und stellt einen Zusammenhang zwischen Galois-Gruppen, Idealgruppen und Normen her. Das quadratische Reziprozitätsgesetz ergibt sich als Spezialfall, indem man die quadratische Erweiterung ℚ(√p*) mit p* = (−1)^((p−1)/2)p betrachtet. Damit steht das quadratische Gesetz an einer grundlegenden Stufe einer umfassenden Theorie der Reziprozität.