# Restklassenring/Z/Quadratische Reste/Einführung/Textabschnitt

Modulo $2$ ist jede Zahl ein quadratischer Rest. Für ungerade Primzahlen kann man ebenfalls sofort eine Aussage über die Anzahl der Quadratreste machen.

## 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$

## Bemerkung

Wenn zu einer Primzahl $p$ eine primitive Einheit $g\in {\left(\mathbb {Z} /(p)\right)}^{\times }$ vorliegt, so hat man einen Gruppenisomorphismus
    ${\left(\mathbb {Z} /(p-1),0,+\right)}\longrightarrow {\left({\left(\mathbb {Z} /(p)\right)}^{\times },1,\cdot \right)},\,i\longmapsto g^{i}.$
Dabei entsprechen die Quadrate rechts denjenigen Elementen links, die ein Vielfaches der $2$ sind. Bei $p$ ungerade besitzt die Hälfte der Elemente links diese Eigenschaft. Insbesondere ist ein Element $k\in {\left(\mathbb {Z} /(p)\right)}^{\times }$ genau dann ein Quadratrest, wenn es von der Form
    $k=g^{2j}\,$
ist.

## Definition

Für eine ungerade Primzahl $p$ und eine zu $p$ teilerfremde Zahl $k\in \mathbb {Z}$ definiert man das Legendre-Symbol, geschrieben $\left({\frac {k}{p}}\right)$ (sprich „$k$ nach $p$“), durch
    $\left({\frac {k}{p}}\right):={\begin{cases}1,{\text{ falls }}k{\text{ quadratischer Rest modulo }}p{\text{ ist}},\\-1,{\text{ falls }}k{\text{ kein quadratischer Rest modulo }}p{\text{ ist}}.\end{cases}}\,$
Insbesondere ist $\left({\frac {k}{p}}\right)=\left({\frac {k\mod p}{p}}\right)$. Die Werte des Legendre-Symbols, also $1$ und $-1$, kann man dabei in $\mathbb {Z}$, in $\mathbb {Z} ^{\times }$ oder in ${\left(\mathbb {Z} /(p)\right)}^{\times }$ auffassen. Für Vielfache von $p$ definierte man manchmal das Legendre-Symbol ebenfalls, und zwar mit dem Wert $0$.

## Lemma

Es sei $p$ eine ungerade Primzahl.
Dann ist die Abbildung
ein Gruppenhomomorphismus.

### Beweis

Die Quadrate bilden offenbar eine Untergruppe in der Einheitengruppe ${\left(\mathbb {Z} /(p)\right)}^{\times }$, die nach Fakt den Index $2$ besitzt. Daher ist
    ${\left(\mathbb {Z} /(p)\right)}^{\times }/{\text{Quadrate}}\cong \mathbb {Z} /(2)\cong \{\pm 1\}\,$
und die Restklassenabbildung ist gerade die Abbildung auf das Legendre-Symbol.
$\Box$
Die folgende Aussage heißt das Euler-Kriterium für quadratische Reste.

## Satz

Es sei $p$ eine ungerade Primzahl.
Dann gilt für eine zu $p$ teilerfremde Zahl $k$ die Gleichheit

### Beweis

Es ist ${\left(k^{\frac {p-1}{2}}\right)}^{2}=k^{p-1}=1$ nach Fakt. Daher ist
    $k^{\frac {p-1}{2}}=\pm 1\,.$
Die Abbildung
    ${\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow \{\pm 1\},\,k\longmapsto k^{\frac {p-1}{2}},$
ist (wie jedes Potenzieren) ein Gruppenhomomorphismus. Die Quadrate werden darunter auf $1$ abgebildet, da für $k=x^{2}$ die Gleichheit
    $k^{\frac {p-1}{2}}=(x^{2})^{\frac {p-1}{2}}=x^{p-1}=1\,$
gilt. Da nach Fakt die Einheitengruppe ${\left(\mathbb {Z} /(p)\right)}^{\times }$ zyklisch ist, muss diese Abbildung surjektiv sein (sonst hätte jedes Element eine kleinere Ordnung). Damit muss diese Abbildung mit der durch das Legendre-Symbol gegebenen übereinstimmen.
$\Box$