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

(\frac{a}{p}) = {\begin{matrix} 1, & wenn a quadratischer Rest modulo p und kein Vielfaches von p ist, \\ - 1, & wenn a quadratischer Nichtrest modulo p ist, \\ 0, & wenn a ein Vielfaches von p ist . \end{matrix}

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:

(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (\mod p)

.

Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff mit

(\frac{a}{p}) = sgn (π_{a, p}),

wobei $π_{a, p}$ , die durch

π_{a, p} (k) \equiv a \cdot k (\mod p)

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

Beispiele

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

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

5 ist quadratischer Nichtrest modulo 7:

(\frac{5}{7}) \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):

(\frac{14}{7}) \equiv 1 4^{\frac{7 - 1}{2}} = 1 4^{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 (\mod p) \Rightarrow (\frac{a}{p}) = (\frac{b}{p})$
$(\frac{a}{p}) \cdot (\frac{b}{p}) = (\frac{a \cdot b}{p})$
$\sum_{k = 1}^{p - 1} (\frac{k}{p}) = 0$ .

Spezielle Werte

Es gilt

(\frac{1}{p}) = 1,

(\frac{2}{p}) = (- 1)^{\frac{p^{2} - 1}{8}} = {\begin{matrix} 1, & für p \equiv 1 oder 7 (\mod 8), \\ - 1, & für p \equiv 3 oder 5 (\mod 8), \end{matrix}

(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}} = {\begin{matrix} 1, & für p \equiv 1 (\mod 4), \\ - 1, & für p \equiv 3 (\mod 4) . \end{matrix}

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

(\frac{10}{31}) = (\frac{2}{31}) (\frac{5}{31}) = 1 \cdot (- 1)^{\frac{5 - 1}{2} \frac{31 - 1}{2}} (\frac{31}{5}) = (\frac{1}{5}) = 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:

(\frac{a}{3}) \equiv a^{\frac{3 - 1}{2}} \mod 3 = a \mod 3

Andererseits gilt auch:

(\frac{3}{p}) = \prod_{l = 1}^{\frac{p - 1}{2}} [3 - 4 \sin^{2} (\frac{2 π l}{p})]

Besonderheiten bei Primzahlen

Siehe dazu unter Pythagoreische Primzahl.