Quadratische Reste und Reziprozitäts­gesetz

Die lineare Kongruenz $ax\equiv b(\mathrm{mod}m)$ löst man mit dem modularen Inversen. Bei $x^2\equiv a(\mathrm{mod}p)$ ist schon die Frage schwieriger, ob es überhaupt eine Lösung gibt. Modulo $7$ hat zum Beispiel $x^2\equiv 2$ die Lösungen $x=3$ und $x=4$ (denn $3^2=9\equiv 2$ und $4^2=16\equiv 2$), die Gleichung $x^2\equiv 3$ dagegen keine. Im Folgenden ist $p$ immer eine ungerade Primzahl.

Modulo $7$ rechnest du $1^2=1$, $2^2=4$, $3^2\equiv 2$, $4^2\equiv 2$, $5^2\equiv 4$, $6^2\equiv 1$. Die quadratischen Reste sind $\{1,2,4\}$, die Nichtreste $\{3,5,6\}$. Das ist kein Zufall: Weil $x^2\equiv y^2$ genau dann gilt, wenn $x\equiv \pm y$ (in einem Körper hat $(x-y)(x+y)\equiv 0$ nur diese Lösungen), liefern die $p-1$ Zahlen $1,\dots ,p-1$ genau $\frac{p-1}{2}$ verschiedene Quadrate. Es gibt also gleich viele Reste wie Nichtreste.

Das Euler-Kriterium

Beweis. Nach dem kleinen Satz von Fermat ist ${(a^{(p-1)/2})}^2=a^{p-1}\equiv 1$, also $a^{(p-1)/2}\equiv \pm 1$. Ist $a\equiv x^2$ ein Rest, dann ist $a^{(p-1)/2}\equiv x^{p-1}\equiv 1$. Das Polynom $X^{(p-1)/2}-1$ hat höchstens $\frac{p-1}{2}$ Nullstellen modulo $p$, und alle $\frac{p-1}{2}$ Reste sind welche davon. Für einen Nichtrest muss deshalb $a^{(p-1)/2}\equiv -1$ gelten. $\square$

Aus dem Kriterium folgt sofort die Regel $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$: Reste mal Reste und Nichtreste mal Nichtreste sind Reste, ein Rest mal ein Nichtrest ist ein Nichtrest. Ebenso folgt der erste Ergänzungssatz $\left(\frac{-1}{p}\right)={(-1)}^{(p-1)/2}$. Die Zahl $-1$ ist also genau dann ein Rest, wenn $p\equiv 1(\mathrm{mod}4)$. Der zweite Ergänzungssatz lautet $\left(\frac{2}{p}\right)={(-1)}^{(p^2-1)/8}$: Die $2$ ist ein Rest für $p\equiv \pm 1(\mathrm{mod}8)$ und ein Nichtrest für $p\equiv \pm 3(\mathrm{mod}8)$.

Das quadratische Reziprozitätsgesetz

Der Beweis ist länger als alle bisherigen Argumente dieser Seite; er benutzt das Lemma von Gauß oder Gaußsche Summen und steht in jedem Lehrbuch der elementaren Zahlentheorie. Wichtig ist, wie du das Gesetz anwendest: Du vertauschst oben und unten, reduzierst die obere Zahl modulo der unteren und holst mit den Ergänzungssätzen Faktoren $2$ und $-1$ heraus. Das ähnelt dem euklidischen Algorithmus. Mit dem Jacobi-Symbol (siehe unten) braucht man dabei sogar keine Primfaktorzerlegung mehr.

Wurzeln modulo p

Für $p\equiv 3(\mathrm{mod}4)$ gibt es eine Formel: Ist $a$ ein Rest, dann löst $x=a^{(p+1)/4}$ die Gleichung $x^2\equiv a$. Beweis. $x^2=a^{(p+1)/2}=a·a^{(p-1)/2}\equiv a·1$ nach dem Euler-Kriterium. Beispiel: $x^2\equiv 2(\mathrm{mod}23)$. Wegen $23\equiv 7(\mathrm{mod}8)$ ist die $2$ ein Rest, und $x=2^6=64\equiv 18\equiv -5$. Probe: $5^2=25\equiv 2$. Die beiden Lösungen sind $x\equiv \pm 5$.

Das Reziprozitätsgesetz lässt sich auf zusammengesetzte untere Zahlen erweitern. Das Jacobi-Symbol $\left(\frac{a}{n}\right)$ ist das Produkt der Legendre-Symbole zu den Primfaktoren von $n$ und gehorcht denselben Rechenregeln. Es wird in Primzahltests wie dem von Solovay und Strassen benutzt.

Zur Geschichte

Leonhard Euler kannte das Gesetz als Vermutung. Adrien-Marie Legendre gab 1785 einen unvollständigen Beweis und führte 1798 in seinem „Essai sur la théorie des nombres“ das nach ihm benannte Symbol ein. Carl Friedrich Gauß fand 1796 einen vollständigen Beweis und veröffentlichte ihn 1801 in den „Disquisitiones Arithmeticae“. Er nannte den Satz das „Fundamentaltheorem“, später auch das „Theorema aureum“, und gab insgesamt acht verschiedene Beweise. Heute sind über 300 Beweise bekannt.