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

${\displaystyle {\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 ${\displaystyle {}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“, so dass wir den Kern bestimmen müssen. Der Kern besteht aus allen Elementen ${\displaystyle {}x}$ mit ${\displaystyle {}x^{2}=1}$. Dazu gehören ${\displaystyle {}1}$ und ${\displaystyle {}-1}$, und diese beiden Elemente sind verschieden, da ${\displaystyle {}p}$ ungerade ist. Aus der polynomialen Identität ${\displaystyle {}x^{2}-1=(x+1)(x-1)}$ folgt, dass es keine weiteren Lösungen geben kann. Der Kern besteht also aus genau ${\displaystyle {}2}$ Elementen und damit besteht das Bild aus ${\displaystyle {}{\frac {p-1}{2}}}$ Elementen.

Die Quadrate bilden offenbar eine Untergruppe in der Einheitengruppe ${\displaystyle {}(\mathbb {Z} /(p))^{\times }}$, die nach Satz 7.1 den Index ${\displaystyle {}2}$ besitzt. Daher ist

${\displaystyle {}{\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.

Es ist ${\displaystyle {}{\left(k^{\frac {p-1}{2}}\right)}^{2}=k^{p-1}=1}$ nach Lemma 4.6. Daher ist

${\displaystyle {}k^{\frac {p-1}{2}}=\pm 1\,.}$

Die Abbildung

${\displaystyle {\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 ${\displaystyle {}1}$ abgebildet, da für ${\displaystyle {}k=x^{2}}$ die Gleichheit

${\displaystyle {}k^{\frac {p-1}{2}}=(x^{2})^{\frac {p-1}{2}}=x^{p-1}=1\,}$

gilt. Da nach Satz 5.11 die Einheitengruppe ${\displaystyle {}{\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.

Die Gleichung von links und rechts wurde bereits in Satz 6.7 bewiesen. Die erste Gleichung ist auch ein Spezialfall von Satz 7.4 und die zweite Gleichung ist elementar.

Es sei ${\displaystyle {}s_{i}\in S_{+}}$ durch die Bedingung

${\displaystyle ik=\epsilon _{i}s_{i}\mod p}$

festgelegt. Wir betrachten alle Vielfachen ${\displaystyle {}jk}$, ${\displaystyle {}j\in S=(\mathbb {Z} /(p))^{\times }}$. Die Menge all dieser Vielfachen ist selbst ganz ${\displaystyle {}S}$, da ja ${\displaystyle {}k}$ eine Einheit und daher die Multiplikation mit ${\displaystyle {}k}$ eine Bijektion ist. Es ist ${\displaystyle {}(-i)k=-ik=-\epsilon _{i}s_{i}}$ für ${\displaystyle {}i\in S_{+}=\{1,\ldots ,t\}}$. Daher ist ${\displaystyle {}S_{+}=\{1,\ldots ,t\}=\{s_{1},\ldots ,s_{t}\}}$. Deshalb gilt ${\displaystyle {}t!=\prod _{i=1}^{t}s_{i}}$ und somit

${\displaystyle {}t!k^{t}={\left(\prod _{i=1}^{t}i\right)}{\left(\prod _{i=1}^{t}k\right)}=\prod _{i=1}^{t}ik=\prod _{i=1}^{t}\epsilon _{i}s_{i}={\left(\prod _{i=1}^{t}\epsilon _{i}\right)}{\left(\prod _{i=1}^{t}s_{i}\right)}={\left(\prod _{i=1}^{t}\epsilon _{i}\right)}t!\mod p\,.}$

Durch kürzen mit ${\displaystyle {}t!}$ (das ist eine Einheit) ergibt sich

${\displaystyle {}k^{t}=\prod _{i=1}^{t}\epsilon _{i}\mod p\,,}$

und das Euler-Kriterium, nämlich

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

liefert das Ergebnis.

Wir benutzen Fakt ***** und haben zu bestimmen, wie viele der Zahlen ${\displaystyle {}2i}$, ${\displaystyle {}i=1,\ldots ,t={\frac {p-1}{2}}}$, in ${\displaystyle {}S_{-}}$ liegen. Nun ist ${\displaystyle {}2i\in S_{-}}$ genau dann, wenn ${\displaystyle {}2i>{\frac {p-1}{2}}}$ ist (alle zu betrachtenden Vielfachen von ${\displaystyle {}2}$ sind kleiner als ${\displaystyle {}p}$). Dies ist äquivalent zu ${\displaystyle {}i>{\frac {p-1}{4}}}$ und wir haben das kleinste ${\displaystyle {}i}$ mit dieser Eigenschaft zu finden. Ist ${\displaystyle {}p-1}$ ein Vielfaches von ${\displaystyle {}4}$, so ist ${\displaystyle {}{\frac {p-1}{4}}+1}$ das kleinste ${\displaystyle {}i}$ und insgesamt gibt es in diesem Fall

${\displaystyle {}{\frac {p-1}{2}}-{\left({\frac {p-1}{4}}+1\right)}+1={\frac {p-1}{4}}\,}$

solche ${\displaystyle {}i}$. Diese Anzahl ist bei ${\displaystyle {}p=1\mod 8}$ gerade und bei ${\displaystyle {}p=5\mod 8}$ ungerade, was das Ergebnis in diesen Fällen ergibt.

Sei also nun ${\displaystyle {}p=3,7\mod 8}$ bzw. ${\displaystyle {}p=3\mod 4}$. Dann ist das kleinste ${\displaystyle {}i}$ derart, dass ${\displaystyle {}2i>{\frac {p-1}{2}}}$ ist, gleich ${\displaystyle {}{\frac {p-1}{4}}+{\frac {1}{2}}}$, und es gibt insgesamt

${\displaystyle {}{\frac {p-1}{2}}-{\left({\frac {p-1}{4}}+{\frac {1}{2}}\right)}+1={\frac {p-1}{4}}+{\frac {1}{2}}={\frac {p+1}{4}}\,}$

solche ${\displaystyle {}i}$. Diese Anzahl ist bei ${\displaystyle {}p=3\mod 8}$ ungerade und bei ${\displaystyle {}p=7\mod 8}$ gerade, was die Behauptung in diesen Fällen ergibt.