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 (\mathbb {Z} /(p))^{\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

${\left(\mathbb {Z} /(p)\right)}^{\times }\longrightarrow \{\pm 1\},\,k\longmapsto \left({\frac {k}{p}}\right),$

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

$\left({\frac {k}{p}}\right)=k^{\frac {p-1}{2}}\mod p.$

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$