Legendre-Symbol

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten | Quelltext bearbeiten]

Das Legendre-Symbol gibt an, ob die Zahl quadratischer Rest modulo p oder quadratischer Nichtrest modulo p ist. Dabei muss 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[Bearbeiten | Quelltext bearbeiten]

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 des Moduls 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

eine Permutation der Zahlen von bis darstellt und das Vorzeichen einer Permutation bezeichnet.

Beispiele[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Das quadratische Reziprozitätsgesetz macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.

Es seien nun und eine Primzahl. Dann gelten folgende Rechenregeln:

  • für .

Die besondere Stellung der Zahl 3[Bearbeiten | Quelltext bearbeiten]

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: