Symmetrie und Anzahl

Quadratische Reste · Abschnitt 42 von 64

Satz

Vorzeichensymmetrie

Für jeden Rest $r$ gilt $r^2\equiv(-r)^2\pmod m$ . Deshalb genügen in einer Tabelle Vertreter der Vorzeichenpaare.

Gelöstes Beispiel

Modulo 7

Die Paare $1,6$ , $2,5$ und $3,4$ besitzen jeweils dieselben Quadrate. Zusammen mit 0 entstehen die Quadratreste 0, 1, 2 und 4.

Satz

Genau die Hälfte der Nichtnullreste

Für eine ungerade Primzahl $p$ gibt es genau $(p-1)/2$ von null verschiedene quadratische Reste modulo $p$ .

Beweis

Warum nur Vorzeichen doppeln

Aus $x^2\equiv y^2\pmod p$ folgt $p\mid(x-y)(x+y)$ . Da $p$ prim ist, gilt $x\equiv y$ oder $x\equiv-y$ . Die $p-1$ Nichtnullreste bilden daher exakt $(p-1)/2$ Paare.