Legendre-Symbol

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 a quadratischer Rest modulo p oder quadratischer Nichtrest modulo p ist. Dabei muss a eine ganze Zahl und p eine Primzahl sein.

Es gilt:

\left({\frac  {a}{p}}\right)={\begin{cases}1&{\mbox{wenn }}a{\mbox{ quadratischer Rest modulo }}p{\mbox{ ist}}\\-1&{\mbox{wenn }}a{\mbox{ quadratischer Nichtrest modulo }}p{\mbox{ ist}}\\0&{\mbox{wenn }}a{\mbox{ ein Vielfaches von }}p{\mbox{ ist}}\end{cases}}

Das Legendre-Symbol ist ein Spezialfall des Jacobi-Symbols, das die gleiche Schreibweise hat. Weitere Notationsvarianten für das Legendre-Symbol sind (a/p) und L(a,p).

Berechnung

Das eulersche Kriterium gibt an, wie sich das Legendre-Symbol für eine ungerade Primzahl p berechnen lässt:

\left({\frac  {a}{p}}\right)\equiv a^{{{\frac  {p-1}{2}}}}{\pmod  p}.

Für die einzige gerade Primzahl 2 gilt:

-1 \equiv 1 \pmod 2.

Jede ungerade Zahl ist quadratischer Rest und jede gerade Zahl ist ein Vielfaches von 2, modulo 2 gibt es also keine Nichtreste:

{\displaystyle \left({\frac {a}{2}}\right)=a{\bmod {2}}}.

Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff, nach dem für ungerade Primzahlen

\left(\frac{a}{p}\right) = \operatorname{sgn}(\pi_{a,p})

gilt, wobei \pi_{a,p}, die durch

\pi _{{a,p}}(k)\equiv a\cdot k{\pmod  p}

definierte Permutation der Zahlen von {\displaystyle k=0,\dotsc p-1} ist, und \operatorname{sgn} das Vorzeichen einer Permutation bezeichnet.

Beispiele

2 ist quadratischer Rest modulo 7 – in der Tat ist ja 2\equiv 3^{2}{\pmod  7}:

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

5 ist quadratischer Nichtrest 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 (also weder Rest noch Nichtrest von 7):

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

Rechenregeln

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

Außerdem gelten für alle ganze Zahlen a, b und alle Primzahlen p folgende Rechenregeln:

Spezielle Werte

Für alle ungeraden Primzahlen p gilt

{\displaystyle \left({\frac {1}{p}}\right)=1}
{\displaystyle \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}}}
{\displaystyle \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}}}

Diese speziellen Werte reichen aus, um jedes nicht-verschwindene Legendre-Symbol durch wiederholtes Aufteilen des „Zählers“ in Primfaktoren, Anwenden des quadratischen Reziprozitätsgesetzes und modulo-Reduktion zu berechnen. So ist zum Beispiel

{\displaystyle \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}

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:

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

Andererseits gilt auch:

\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]

Besonderheiten bei Primzahlen

Siehe dazu unter Pythagoreische Primzahl.

Trenner
Basierend auf einem Artikel in: Extern Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 27.01. 2021