Quadratischer Rest

Der quadratische Rest ist der Rest der Division einer Quadratzahl durch eine natürliche Zahl. Eine ganze Zahl $r$ heißt quadratischer Rest modulo $m$, falls es eine Zahl $x$ mit

$r\equiv x^{2}\mod m$

gibt. Ist dies nicht der Fall, spricht man auch von einem quadratischen Nichtrest oder einem nicht-quadratischen Rest.

Beispiel: Quadratische Reste und Nichtreste modulo 4

Die quadratischen Reste und Nichtreste modulo 4 sind:

• quadratische Reste: 0 und 1
• quadratische Nichtreste: 2 und 3

Diese Aussage beweist man mittels einer Fallunterscheidung: man berechnet jeweils die quadratischen Reste der geraden und der ungeraden Zahlen.

Fall 1: Eine gerade Zahl $x$ lässt sich als $x=2k$ mit einer ganzen Zahl $k$ darstellen. Damit berechnet sich $x^{2}$ zu

$x^{2}=(2k)^{2}=4\cdot k^{2}+0$

Damit ist 0 der quadratischen Rest modulo 4 einer geraden Zahl.

Fall 2: Eine ungerade Zahl $x$ lässt sich als $x=2k+1$ mit einer ganzen Zahl $k$ darstellen. Damit berechnet sich $x^{2}$ zu

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle x^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4 \cdot (k^2 + k) + 1}

Damit ist 1 der quadratischen Rest modulo 4 einer ungeraden Zahl.

Da es außer den geraden und ungeraden keine weiteren Zahlen gibt, sind die Zahlen 2 und 3 quadratische Nichtreste modulo 4.

Vereinfachte Berechnung der Quadratzahlen

Für kleinere Zahlen $m$ können die quadratischen Reste relativ rasch berechnet werden: Es genügt, die Zahlen $0\leq x\leq m/2$ zu betrachten, denn $x^{2}$ und $(x+k\cdot m)^{2}$ haben denselben Rest, ebenso $x^{2}$ und $(-x)^{2}$, also auch $x^{2}$ und $(m-x)^{2}$.

Die Berechnung wird hier am Beispiel der Zahl 11 demonstriert.

 0 Mod 11 = 0 ;  1 Mod 11 = 1 ;   4 Mod 11 = 4 ;     9 Mod 11 = 9 
16 Mod 11 = 5 ; 25 Mod 11 = 3 ;  36 Mod 11 = 3 ;    49 Mod 11 = 5 
64 Mod 11 = 9 ; 81 Mod 11 = 4 ; 100 Mod 11 = 1 und 121 Mod 11 = 0.

Man könnte jetzt weitermachen, aber der 0,1,4,9,5,3,3,5,9,4,1-Zyklus wiederholt sich immer wieder. Wegen der Symmetriebeziehung ist nur die Berechnung der Quadratzahlen kleiner 36 erforderlich.

Zur Berechnung der Quadratzahlen kann die Beziehung

$\left({n+1}\right)^{2}=n^{2}+2\cdot n+1$

verwendet werden. Die nächste Quadratzahl kann also durch Addition von $2n+1$ ganz ohne Multiplikation berechnet werden. Damit sind die quadratischen Reste für 11 ganz rasch auch im Kopf zu berechnen.

Multiplikative Eigenschaften

Sind $a$ und $b$ quadratische Reste modulo $m$, also etwa

$a\equiv x^{2}\mod m$ und Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle b\equiv y^2\mod m} ,

so gilt

$ab\equiv (xy)^{2}\mod m,$

es ist also auch $ab$ ein quadratischer Rest.

Der Fall von Primzahlen und das Legendre-Symbol

Im folgenden sei $m=p$ eine Primzahl. Sind $a$ und $b$ nicht durch $p$ teilbar, so gibt die folgende Tabelle in Abhängigkeit von $a$ und $b$ an, ob das Produkt $ab$ quadratischer Rest (R) oder Nichtrest (NR) ist:

	a R	a NR
b R	ab R	ab NR
b NR	ab NR	ab R

Eine andere Formulierung dieser Aussage ist die folgende: Das Legendre-Symbol

$\left({\frac {a}{p}}\right)={\begin{cases}1&a\ \mathrm {quadratischer\ Rest\ modulo} \ p\ \mathrm {und} \ p\nmid a\\-1&a\ \mathrm {quadratischer\ Nichtrest\ modulo} \ p\ \mathrm {und} \ p\nmid a\\0&p\mid a\end{cases}}$

erfüllt die Beziehung

$\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$

für beliebige ganze Zahlen $a,b$.

Für Primzahlen $p>2$ gilt

$\left({\frac {a}{p}}\right)\equiv a^{(p-1)/2}\mod p.$

Aus dieser Beziehung lässt sich auch unmittelbar die folgende Aussage ablesen: $-1$ ist quadratischer Rest modulo Primzahlen der Form $4k+1$ und Nichtrest modulo Primzahlen der Form $4k+3$.