Legendre-Symbol

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.

Definition und Notation

Das Legendre-Symbol gibt an, ob die Zahl $a$ quadratischer Rest modulo $p$ oder quadratischer Nichtrest modulo $p$ ist. Dabei muss $a$ eine ganze Zahl und $p$ eine Primzahl sein.

Es gilt:

$\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 Spezialfall des Jacobi-Symbols, das die gleiche Schreibweise hat. Weitere Notationsvarianten für das Legendre-Symbol sind $(a/p)$ und $L(a,p)$.

Berechnung

Das eulersche Kriterium gibt an, wie sich das Legendre-Symbol für eine ungerade Primzahl $p$ berechnen lässt:

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

Für die einzige gerade Primzahl $2$ gilt:

$-1\equiv 1{\pmod {2}}$.

Jede ungerade Zahl ist quadratischer Rest und jede gerade Zahl ist ein Vielfaches von 2, modulo 2 gibt es also keine Nichtreste:

$\left({\frac {a}{2}}\right)=a{\bmod {2}}$.

Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff, nach dem für ungerade Primzahlen

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

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

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

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

Beispiele

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

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

5 ist quadratischer Nichtrest modulo 7:

$\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):

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

Rechenregeln

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

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

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

Spezielle Werte

Für alle ungeraden Primzahlen $p$ gilt

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

$\left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{2}}={\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}}$

$\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-verschwindene Legendre-Symbol durch wiederholtes Aufteilen des „Zählers“ in Primfaktoren, Anwenden des quadratischen Reziprozitätsgesetzes und modulo-Reduktion zu berechnen. So ist zum Beispiel

$\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 besondere Stellung der Zahl 3

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:

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

Andererseits gilt auch:

$\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]$

Besonderheiten bei Primzahlen

Siehe dazu unter Pythagoreische Primzahl.