Restklassenringe (Z)/Quadratreste/Anzahl/Fakt mit Beweisklappe

Satz

Es sei ${}p$ eine ungerade Primzahl.

Dann gibt es ${}{\frac {p+1}{2}}$ quadratische Reste modulo ${}p$ und ${}{\frac {p-1}{2}}$ nichtquadratische Reste modulo ${}p$.

Beweis

Zunächst ist ${}0$ ein quadratischer Rest. Wir betrachten im Folgenden nur noch die Einheiten in ${}\mathbb {Z} /(p)$ (also die von ${}0$ verschiedenen Reste) und zeigen, dass es darunter gleich viele quadratische und nichtquadratische Reste gibt. Die Abbildung

${\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow {\left(\mathbb {Z} /(p)\right)}^{\times },\,x\longmapsto x^{2},$

ist offenbar ein Gruppenhomomorphismus der Einheitengruppe in sich selbst. Ein Element  ${}k\in {\left(\mathbb {Z} /(p)\right)}^{\times }$  ist genau dann ein Quadratrest, wenn es im Bild dieses Homomorphismus liegt. Nach dem Isomorphiesatz ist „Bild = Urbild modulo Kern“, sodass wir den Kern bestimmen müssen. Der Kern besteht aus allen Elementen ${}x$ mit  ${}x^{2}=1$.  Dazu gehören ${}1$ und ${}-1$, und diese beiden Elemente sind verschieden, da ${}p$ ungerade ist. Aus der polynomialen Identität  ${}x^{2}-1=(x+1)(x-1)$  folgt, dass es keine weiteren Lösungen geben kann. Der Kern besteht also aus genau ${}2$ Elementen und damit besteht das Bild aus ${}{\frac {p-1}{2}}$ Elementen.

$\Box$