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.



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 27.01. 2021