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

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

Bearbeiten

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

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

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

Bearbeiten

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

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:

 

Besonderheiten bei Primzahlen

Bearbeiten

Siehe dazu unter Pythagoreische Primzahl.