Zum Inhalt springen

Benutzer:Arbol01/Legendre-Symbol

Aus Wikibooks

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: