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 muss eine ganze Zahl und eine Primzahl sein.
Es gilt:
Das Legendre-Symbol ist ein Spezialfall des Jacobi-Symbols, das die gleiche Schreibweise hat. Weitere Notationsvarianten für das Legendre-Symbol sind und .
Berechnung
Das eulersche Kriterium gibt an, wie sich das Legendre-Symbol für eine ungerade Primzahl berechnen lässt:
- .
Für die einzige gerade Primzahl gilt:
- .
Jede ungerade Zahl ist quadratischer Rest und jede gerade Zahl ist ein Vielfaches von 2, modulo 2 gibt es also keine Nichtreste:
- .
Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff, nach dem für ungerade Primzahlen
gilt, 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:
- für .
Spezielle Werte
Für alle ungeraden Primzahlen gilt
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
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.
Basierend auf einem Artikel in: Wikipedia.de Seite zurück© biancahoegel.de
Datum der letzten Änderung: Jena, den: 27.01. 2021