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 und wird wie folgt notiert:

$\left({\frac {a}{p}}\right)\qquad (a/p)\qquad L(a,p)$

Diese drei Notationen geben jeweils an, ob die Zahl $a$ ein quadratischer Rest modulo p oder quadratischer Nichtrest modulo p ist. Dabei muss $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.

Das Eulersche Kriterium gibt an, wie sich das Legendre-Symbol für alle Primzahlen $p$ außer der 2 berechnen lässt:

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

Die Zahl 2 wird durch die Formel nicht berücksichtigt, da gilt

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

d.h. alle Zahlen sind entweder Vielfache von 2 oder quadratische Reste modulo 2: $L(a,2)=a\,{\bmod {2}}$.

Beispiele

2 ist ein 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 kein quadratischer Rest 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:

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

Es seien nun $a,b\in \mathbb {Z}$ und $p$ eine Primzahl. Dann gelten 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$, sofern $p\neq 2$.

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)=a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3$

Wenn man also ein Legendre-Symbol in Legendre-Symbole der Form $\left({\frac {a}{3}}\right)$ zerlegen kann, so lässt sich der Wert, den das Legendre-Symbol zurückliefert, leicht berechnen.

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