imported>1234qwer1234qwer4: /* Definition und Notation */ fix

2025-04-19T15:17:45Z

Definition und Notation: fix

Neue Seite

Das '''Legendre-Symbol''' ist eine Kurzschreibweise, die in der [[Zahlentheorie]], einem [[Teilgebiet der Mathematik]], verwendet wird. Es ist nach dem französischen Mathematiker [[Adrien-Marie Legendre]] benannt.

== Definition und Notation ==
Das Legendre-Symbol gibt an, ob die Zahl <math>a</math> [[Quadratischer Rest|quadratischer Rest modulo <math>p</math>]] oder quadratischer Nichtrest modulo <math>p</math> ist. Dabei ist <math>a</math> eine ganze Zahl und <math>p</math> eine ungerade [[Primzahl]].

Es gilt
:<math>\left(\frac{a}{p}\right) = \begin{cases}
1, & \text{wenn } a \text{ quadratischer Rest modulo } p \text{ und kein Vielfaches von }p\text{ ist}, \\
-1, & \text{wenn } a \text{ quadratischer Nichtrest modulo } p \text{ ist}, \\
0, & \text{wenn } a \text{ ein Vielfaches von } p \text{ ist}.
\end{cases}</math>

Das Legendre-Symbol ist ein Spezialisierung des [[Jacobi-Symbol]]s, das wiederum eine Spezialisierung des [[Kronecker-Symbol]]s ist. Alle drei Symbole benutzen daher unmissverständlich dieselbe Schreibweise. Weitere Notationsvarianten für das Legendre-Symbol sind <math>(a/p)</math> und <math>L(a,p)</math>.

== Berechnung ==

Das '''eulersche Kriterium''' gibt eine mögliche Berechnungsmethode zum Legendre-Symbol an:
:<math>\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p</math>.

Eine weitere Berechnungsmöglichkeit liefert das [[Lemma von Zolotareff]] mit
:<math>\left(\frac{a}{p}\right) = \operatorname{sgn}(\pi_{a,p}),</math>
wobei <math>\pi_{a,p}</math>, die durch
:<math>\pi_{a,p}(k) \equiv a \cdot k \pmod p</math>
definierte [[Permutation]] der Zahlen von <math>k = 0, \dotsc p-1</math> ist, und <math>\operatorname{sgn}</math> das [[Vorzeichen (Permutation)|Vorzeichen]] einer Permutation bezeichnet.

== Beispiele ==

2 ist quadratischer Rest modulo 7 – in der Tat ist ja <math>2\equiv 3^2\pmod 7</math>:

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

5 ist quadratischer Nichtrest modulo 7:

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

14 ist durch 7 teilbar (also weder Rest noch Nichtrest von 7):

:<math>\left(\frac{14}{7}\right) \equiv 14^{\frac{7-1}{2}} = 14^3 \equiv 0 \mod7</math>

== Rechenregeln ==

Das [[Quadratisches Reziprozitätsgesetz|quadratische Reziprozitätsgesetz]] macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.

Außerdem gelten für alle ganze Zahlen <math>a</math>, <math>b</math> und alle Primzahlen <math>p</math> folgende Rechenregeln:
* <math>a \equiv b \pmod p \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)</math>
* <math>\left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right) = \left(\frac{a\cdot b}{p}\right)</math>
* <math>\sum_{k=1}^{p-1} \left(\frac{k}{p}\right) = 0</math>.

== Spezielle Werte ==
Es gilt
:<math>\left(\frac{1}{p}\right) = 1,</math>
:<math>\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}} = \begin{cases}
1, & \mbox{ für }p \equiv 1\mbox{ oder }7 \pmod{8}, \\
-1, & \mbox{ für }p \equiv 3\mbox{ oder }5 \pmod{8},
\end{cases}</math>
:<math>\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} =
\begin{cases}
1, & \mbox{ für }p \equiv 1\pmod{4}, \\
-1, & \mbox{ für }p \equiv 3\pmod{4}.
\end{cases}</math>
Diese speziellen Werte reichen aus, um jedes nicht-verschwindende Legendre-Symbol durch wiederholtes Aufteilen des „Zählers“ in Primfaktoren, Anwenden des [[Quadratisches Reziprozitätsgesetz|quadratischen Reziprozitätsgesetzes]] und modulo-Reduktion zu berechnen. So ist zum Beispiel
:<math>\left(\frac{10}{31}\right)=\left(\frac{2}{31}\right)\left(\frac{5}{31}\right)=1\cdot(-1)^{\frac{5-1}{2}\frac{31-1}{2}}\left(\frac{31}{5}\right)=\left(\frac{1}{5}\right)=1.</math>

== Die besondere Stellung der Zahl 3 ==

Die Zahl 3 liefert bei der Ganzzahldivision als Modulo die Werte 0, 1 und −1 zurück. Dies entspricht genau den Werten des Legendre-Symbols. Es gilt also:
:<math>\left(\frac{a}{3}\right) \equiv a^{\frac{3-1}{2}}\ \operatorname{mod}\ 3 = a \ \operatorname{mod}\ 3</math>

Andererseits gilt auch:
:<math>\left(\frac{3}{p}\right) = \prod_{l=1}^{\frac{p-1}{2}} \left[3-4\,\sin^2{\left(\frac{2 \pi l}{p}\right)}\right]</math>

== Besonderheiten bei Primzahlen ==

Siehe dazu unter [[Pythagoreische Primzahl]].

[[Kategorie:Zahlentheorie]]

Legendre-Symbol - Versionsgeschichte

imported>1234qwer1234qwer4: /* Definition und Notation */ fix