Formelsammlung Lexikon Legendre-Symbol


Startseite	Bookmark setzen Sitemap Impressum

» Formelsammlung:

» Startseite

» Astronomie

» Biologie

» BWL

» Chemie

» Informatik

» Mathematik

» Physik

» Interaktiv:

» Forum

» Lexikon

» Mitmachen

» Links zu Uns

» Surftipps

» Informationen:

» Kontakt

» Impressum

» Über Formel-Sammlung.de

» Partnerseiten:

www.schuelerlexikon.de

» Partner:

Etiketten
Kostenlose Kochrezepte
Künstler Verzeichnis
Schilder
Spieleforum
Witze & SMS Sprüche

Legendre-Symbol

Sie befinden Sie in: Formelsammlung Lexikon > l > Legendre-Symbol

Legendre-Symbol

Das Legendre-Symbol gibt von einer 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)

Inhaltsverzeichnis

1 Einleitung

2 Beispiele

3 Regeln und Fakten um das Legendre-Symbol

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

5 Die besondere Stellung der Zahl 3

6 Jacobi-Symbol

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 das Legendre-Symbol gilt nun, für eine Primzahl p und eine dazu teilerfremde, natürliche Zahl a das:

$\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) = 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) = 4^{\frac{7-1}{2}}\mod 7 = 4^3\mod 7 = 1$

5 ist kein quadratischer Rest zu modulo 7:

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

14 ist durch 7 teilbar:

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

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ück liefert. Es gilt also:

$\left(\frac{a}{3}\right) = a \mod 3$

Wenn man also ein Legendre-Symbol so 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)$

Lexikon Eintrag Drucken |

Dokument als PDF downloaden

Dieser Artikel stammt aus Wikipedia, der freien Enzyklopädie
und steht unter der GNU Free Documentation Licence.

zum Seitenanfang

» Unterstüzt von:

» Anzeigen: