Benutzer:Arbol01/Legendre-Symbol

Das Legendre-Symbol gibt von einer natürlichen Zahl a an, ob sie quadratischer Rest oder quadratischer Nichtrest modulo einer Primzahl p mit p>2 ist. Es ist nach dem französischen Mathematiker Adrien-Marie Legendre benannt. Es wird wie folgt notiert:

oder auch (a/p)

Um zwischen dem Legendre-Symbol und dem Jacobi-Symbol zu unterscheiden schreibt man auch L(a,p) und J(a,n)

Einleitung

Bearbeiten

Zusammen mit Leonhard Euler, Carl Friedrich Gauß und Pierre de Fermat hat sich Legendre mit den Quadratischen Diophantischen Gleichungen beschäftigt, und über diese den quadratischen Rest entwickelt:

Wenn zu einer Zahl q modulo p ein x existiert, so dass gilt:
 
dann ist q ein quadratischer Rest, sonst nicht.
Beispiel: Zur Primzahl p=7 sind die Zahlen 1, 2, 4 und 0 quadratische Reste. 3, 5 und 6 sind zur 7 keine quadratischen Reste.


Für eine Primzahl p und eine dazu teilerfremde, natürliche Zahl a ist das Legendresymbol definiert als

 

Euler hat nun gezeigt, dass

 

gilt, wenn p eine ungerade Primzahl ist.

Beispiele

Bearbeiten
4 ist ein quadratischer Rest zu modulo 7:
 
5 ist kein quadratischer Rest zu modulo 7:
 
14 ist durch 7 teilbar:
 


Das quadratische Reziprozitätsgesetz gibt eine Möglichkeit an, wie man das Legendre-Symbol berechnen kann.

Regeln und Fakten um das Legendre-Symbol

Bearbeiten
  •  


  • Wenn   und  , dann folgt daraus:  


  •  


  •  


  • Wenn  


  • Aus den vorherigen beiden Punkten folgt, dass   gilt.


  • Für eine Quadratzahl q und eine Primzahl p mit p>2 gilt:  

Warum muss die Primzahl p größer 2 sein?

Bearbeiten

Für die Zahl 2 gilt, dass sie in der ganzzahligen Division nur die 1 und 0 als Modulo zurückliefern kann. Daraus folgt zwangsläufig, dass   gilt.

Die besondere Stellung der Zahl 3

Bearbeiten

Die Zahl 3 liefert bei der Ganzzahldivision als Modulo die Werte 0, 1 und -1 zurück. Dabei passen die Werte genau zu denen, die das Legendre-Symbol, beziehungsweise die dahinter steckende Funktion, zurückliefert. Es gilt also:

 

Wenn man also ein Legendre-Symbol in Legendre-Symbole der Form   zerlegen kann, so lässt sich der Wert, den das Legendre-Symbol zurückliefert, leicht berechnen.

Jacobi-Symbol

Bearbeiten

Das Jacobi-Symbol ist eine Erweiterung des Legendre-Symbols, in der Art, dass statt der Primzahl p wie bei (a/p) auch eine zusammengesetzte Zahl b eingesetzt werden kann. Da b die Primfaktorzerlegung b=p1*p2*... besitzt, sieht das dazugehörige
Jacobi-Symbol

 

Beispiel: