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:

$\left({\frac {a}{p}}\right)$ 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

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:

$x^{2}\equiv q\mod p$

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

$\left({\frac {a}{p}}\right)=\left\{{\begin{matrix}1&{\mbox{wenn }}a{\mbox{ ein quadratischer Rest zu }}p{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ kein quadratischer Rest zu }}p{\mbox{ ist}}\\0&{\mbox{wenn }}a{\mbox{ und }}p{\mbox{ nicht teilerfremd sind und }}p\ a{\mbox{ teilt}}\end{matrix}}\right.$

Euler hat nun gezeigt, dass

$\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}\mod p$

gilt, wenn p eine ungerade Primzahl ist.

Beispiele

4 ist ein quadratischer Rest zu modulo 7:

$\left({\frac {4}{7}}\right)\equiv 4^{\frac {7-1}{2}}=4^{3}\equiv 1\mod 7$

5 ist kein quadratischer Rest zu modulo 7:

$\left({\frac {5}{7}}\right)\equiv 5^{\frac {7-1}{2}}=5^{3}\equiv 6\equiv -1\mod 7$

14 ist durch 7 teilbar:

$\left({\frac {14}{7}}\right)\equiv 14^{\frac {7-1}{2}}=14^{3}\equiv 0\mod 7$

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

Regeln und Fakten um das Legendre-Symbol

• $\left({\frac {-1}{p}}\right)=\left\{{\begin{matrix}1&{\mbox{wenn }}p\equiv 1(\mod 4)\\-1&{\mbox{wenn }}p\equiv -1(\mod 4)\end{matrix}}\right.$

• Wenn $\left({\frac {a}{p}}\right)=-1$ und $\left({\frac {b}{p}}\right)=-1$, dann folgt daraus: $\left({\frac {a}{p}}\right)*\left({\frac {b}{p}}\right)=-1*-1=1$

• $\left({\frac {a}{p}}\right)*\left({\frac {b}{p}}\right)=\left({\frac {a*b}{p}}\right)$

• $\left({\frac {a}{p}}\right)+\left({\frac {n*p}{p}}\right)=\left({\frac {a+n*p}{p}}\right)$

• Wenn $a\equiv b\ \operatorname {mod} \ p\ \ \Rightarrow \ \ \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$

• Aus den vorherigen beiden Punkten folgt, dass $\left({\frac {a}{p}}\right)=\left({\frac {a+n*p}{p}}\right)$ gilt.

• Für eine Quadratzahl q und eine Primzahl p mit p>2 gilt: $\left({\frac {q}{p}}\right)=1$

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

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 $-1\equiv 1\mod 2$ gilt.

Die besondere Stellung der Zahl 3

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:

$\left({\frac {a}{3}}\right)=a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3$

Wenn man also ein Legendre-Symbol in Legendre-Symbole der Form $\left({\frac {a}{3}}\right)$ zerlegen kann, so lässt sich der Wert, den das Legendre-Symbol zurückliefert, leicht berechnen.

Jacobi-Symbol

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=p₁*p₂*... besitzt, sieht das dazugehörige
Jacobi-Symbol

$\left({\frac {a}{b}}\right)=\left({\frac {a}{p_{1}}}\right)*\left({\frac {a}{p_{2}}}\right)*...$

Beispiel:

$\left({\frac {a}{105}}\right)=\left({\frac {a}{3}}\right)*\left({\frac {a}{5}}\right)*\left({\frac {a}{7}}\right)$