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 ist $a$ eine ganze Zahl und $p$ eine ungerade Primzahl.

Es gilt

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

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 $(a/p)$ und $L(a,p)$.

Berechnung

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

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

Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff mit

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

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

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

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

Beispiele

2 ist quadratischer Rest modulo 7 – in der Tat ist ja $2\equiv 3^2(\mathrm{mod}7)$:

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

5 ist quadratischer Nichtrest modulo 7:

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

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 0mod7$

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(\mathrm{mod}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$.

Spezielle Werte

Es gilt

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

$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{cc}1,& \text{ für }p\equiv 1\text{ oder }7(\mathrm{mod}8),\\ -1,& \text{ für }p\equiv 3\text{ oder }5(\mathrm{mod}8),\end{array}$

$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{cc}1,& \text{ für }p\equiv 1(\mathrm{mod}4),\\ -1,& \text{ für }p\equiv 3(\mathrm{mod}4).\end{array}$

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

$\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}}\mathrm{mod}3=a\mathrm{mod}3$

Andererseits gilt auch:

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

Besonderheiten bei Primzahlen

Siehe dazu unter Pythagoreische Primzahl.