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 quadratischer Rest modulo oder quadratischer Nichtrest modulo ist. Dabei ist eine ganze Zahl und eine ungerade Primzahl.
Es gilt
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 und .
Berechnung
Das eulersche Kriterium gibt eine mögliche Berechnungsmethode zum Legendre-Symbol an:
- .
Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff mit
wobei , die durch
definierte Permutation der Zahlen von ist, und das Vorzeichen einer Permutation bezeichnet.
Beispiele
2 ist quadratischer Rest modulo 7 – in der Tat ist ja :
5 ist quadratischer Nichtrest modulo 7:
14 ist durch 7 teilbar (also weder Rest noch Nichtrest von 7):
Rechenregeln
Das quadratische Reziprozitätsgesetz macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.
Außerdem gelten für alle ganze Zahlen , und alle Primzahlen folgende Rechenregeln:
- .
Spezielle Werte
Es gilt
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
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:
Andererseits gilt auch:
Besonderheiten bei Primzahlen
Siehe dazu unter Pythagoreische Primzahl.