Legendre-Symbol

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 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[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 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[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.

Außerdem gelten für alle ganze Zahlen , und alle Primzahlen 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: