Eulersches Kriterium

Das Legendre-Symbol ist eine Kurzschreibweise, die in der Zahlentheorie, einem Teilgebiet der Mathematik, verwendet wird. Es ist nach dem französischen Mathematiker Adrien-Marie Legendre benannt.

Das Legendre-Symbol gibt an, ob die Zahl ${\displaystyle a}$ quadratischer Rest modulo ${\displaystyle p}$ oder quadratischer Nichtrest modulo ${\displaystyle p}$ ist. Dabei ist ${\displaystyle a}$ eine ganze Zahl und ${\displaystyle p}$ eine ungerade Primzahl.

Es gilt

${\displaystyle \left({\frac {a}{p}\right)={\begin{cases}1,&{\mbox{wenn }a{\mbox{ quadratischer Rest modulo }p{\mbox{ ist},\\-1,&{\mbox{wenn }a{\mbox{ quadratischer Nichtrest modulo }p{\mbox{ ist},\\0,&{\mbox{wenn }a{\mbox{ ein Vielfaches von }p{\mbox{ ist}.\end{cases}$

Das Legendre-Symbol ist ein Spezialisierung des Jacobi-Symbols, das wiederum eine Spezialisierung des Kronecker-Symbols ist. Alle drei Symbole benutzen daher unmissverständlich dieselbe Schreibweise. Weitere Notationsvarianten für das Legendre-Symbol sind ${\displaystyle (a/p)}$ und ${\displaystyle L(a,p)}$.

Das eulersche Kriterium gibt eine mögliche Berechnungsmethode zum Legendre-Symbol an:

${\displaystyle \left({\frac {a}{p}\right)\equiv a^{\frac {p-1}{2}{\pmod {p}$.

Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff mit

${\displaystyle \left({\frac {a}{p}\right)=\operatorname {sgn} (\pi _{a,p}),}$

wobei ${\displaystyle \pi _{a,p}$, die durch

${\displaystyle \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}$

definierte Permutation der Zahlen von ${\displaystyle k=0,\dotsc p-1}$ ist, und ${\displaystyle \operatorname {sgn} }$ das Vorzeichen einer Permutation bezeichnet.

2 ist quadratischer Rest modulo 7 – in der Tat ist ja ${\displaystyle 2\equiv 3^{2}{\pmod {7}$:

${\displaystyle \left({\frac {2}{7}\right)\equiv 2^{\frac {7-1}{2}=2^{3}\equiv 1\mod 7}$

5 ist quadratischer Nichtrest modulo 7:

${\displaystyle \left({\frac {5}{7}\right)\equiv 5^{\frac {7-1}{2}=5^{3}\equiv 6\equiv -1\mod 7}$

14 ist durch 7 teilbar (also weder Rest noch Nichtrest von 7):

${\displaystyle \left({\frac {14}{7}\right)\equiv 14^{\frac {7-1}{2}=14^{3}\equiv 0\mod 7}$

Das quadratische Reziprozitätsgesetz macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.

Außerdem gelten für alle ganze Zahlen ${\displaystyle a}$, ${\displaystyle b}$ und alle Primzahlen ${\displaystyle p}$ folgende Rechenregeln:

• ${\displaystyle a\equiv b{\pmod {p}\Rightarrow \left({\frac {a}{p}\right)=\left({\frac {b}{p}\right)}$
• ${\displaystyle \left({\frac {a}{p}\right)\cdot \left({\frac {b}{p}\right)=\left({\frac {a\cdot b}{p}\right)}$
• ${\displaystyle \sum _{k=1}^{p-1}\left({\frac {k}{p}\right)=0}$.

Es gilt

${\displaystyle \left({\frac {1}{p}\right)=1,}$

${\displaystyle \left({\frac {2}{p}\right)=(-1)^{\frac {p^{2}-1}{8}={\begin{cases}1,&{\mbox{ für }p\equiv 1{\mbox{ oder }7{\pmod {8},\\-1,&{\mbox{ für }p\equiv 3{\mbox{ oder }5{\pmod {8},\end{cases}$

${\displaystyle \left({\frac {-1}{p}\right)=(-1)^{\frac {p-1}{2}={\begin{cases}1,&{\mbox{ für }p\equiv 1{\pmod {4},\\-1,&{\mbox{ für }p\equiv 3{\pmod {4}.\end{cases}$

Diese speziellen Werte reichen aus, um jedes nicht-verschwindende Legendre-Symbol durch wiederholtes Aufteilen des „Zählers“ in Primfaktoren, Anwenden des quadratischen Reziprozitätsgesetzes und modulo-Reduktion zu berechnen. So ist zum Beispiel

${\displaystyle \left({\frac {10}{31}\right)=\left({\frac {2}{31}\right)\left({\frac {5}{31}\right)=1\cdot (-1)^{\frac {5-1}{2}{\frac {31-1}{2}\left({\frac {31}{5}\right)=\left({\frac {1}{5}\right)=1.}$

Die Zahl 3 liefert bei der Ganzzahldivision als Modulo die Werte 0, 1 und −1 zurück. Dies entspricht genau den Werten des Legendre-Symbols. Es gilt also:

${\displaystyle \left({\frac {a}{3}\right)\equiv a^{\frac {3-1}{2}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3}$

Andererseits gilt auch:

${\displaystyle \left({\frac {3}{p}\right)=\prod _{l=1}^{\frac {p-1}{2}\left[3-4\,\sin ^{2}{\left({\frac {2\pi l}{p}\right)}\right]}$

Siehe dazu unter Pythagoreische Primzahl.