Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 21. November 2019 

Legendre-Symbol


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Das Legendre-Symbol gibt von einer Zahl a an ob sie quadratischer Rest oder Nichtrest modulo einer Primzahl p mit p>2 ist. Es ist nach französischen Mathematiker Adrien-Marie Legendre benannt. Es wird wie folgt notiert:

<math>\left(\frac{a}{p}\right)</math> oder auch (a/p)

Inhaltsverzeichnis

Einleitung

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

Wenn zu einer Zahl q modulo p ein x existiert so dass gilt:
<math>x^2 \equiv q \mod p</math>
dann ist q ein quadratischer Rest sonst nicht.

Beispiel: Zur Primzahl p=7 sind die Zahlen 2 4 und 0 quadratische Reste. 3 und 6 sind zur 7 keine quadratischen

Für das Legendre-Symbol gilt nun für Primzahl p und eine dazu teilerfremde natürliche Zahl a das:

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

Euler hat nun gezeigt dass

<math>\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}}\mod p</math>

gilt wenn p eine ungerade Primzahl ist.

Beispiele

4 ist ein quadratischer Rest zu modulo

<math>\left(\frac{4}{7}\right) = 4^{\frac{7-1}{2}}\mod 7 = 4^3\mod 7 1 </math>

5 ist kein quadratischer Rest zu modulo

<math>\left(\frac{5}{7}\right) = 5^{\frac{7-1}{2}} \mod 7 = 5^3 7 = 6 \mod 7 \equiv -1 7 </math>

14 ist durch 7 teilbar:
<math>\left(\frac{14}{7}\right) = 14^{\frac{7-1}{2}} \mod 7 = 14^3 7 = 0 </math>

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

Regeln und Fakten um das Legendre-Symbol

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

  • Wenn <math>\left(\frac{a}{p}\right) = -1</math> und <math>\left(\frac{b}{p}\right) = dann folgt daraus: <math>\left(\frac{a}{p}\right) * \left(\frac{b}{p}\right) = * -1 = 1</math>

  • <math>\left(\frac{a}{p}\right) * \left(\frac{b}{p}\right) = \left(\frac{a*b}{p}\right)</math>

  • <math>\left(\frac{a}{p}\right) + \left(\frac{n*p}{p}\right) = \left(\frac{a+n*p}{p}\right)</math>

  • Wenn <math>a\equiv b\ \operatorname{mod}\ p \ \ \ \ \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)</math>

  • Aus den vorherigen beiden Punkten folgt das = \left(\frac{a+n*p}{p}\right)</math> gilt.

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

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

Für die Zahl 2 gilt daß in der ganzzahligen Division nur die 1 0 als Modulo zurückliefern kann. Daraus folgt das <math> -1 \equiv 1 ( \mod gilt.

Die besondere Stellung der Zahl 3

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

<math>\left(\frac{a}{3}\right) = a \mod 3 </math>

Wenn man also ein Legendre-Symbol so Legendre-Symbole der Form: :<math>\left(\frac{a}{3}\right)</math> zerlegen kann so sich der Wert den das Legendre-Symbol zurückliefert berechnen.

  

Jacobi-Symbol

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

<math>\left(\frac{a}{b}\right)=\left(\frac{a}{p_1}\right)*\left(\frac{a}{p_2}\right)*...</math>

Beispiel:

<math>\left(\frac{a}{105}\right)=\left(\frac{a}{3}\right)*\left(\frac{a}{5}\right)*\left(\frac{a}{7}\right)</math>



Bücher zum Thema Legendre-Symbol

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Legendre-Symbol.html">Legendre-Symbol </a>