Restklassenringe (Z)/Quadratreste/Euler Kriterium/Fakt mit Beweisklappe

Euler Kriterium

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$