Legendre-Symbol

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Das Legendre-Symbol gibt an, ob die Zahl a quadratischer Rest modulo p oder quadratischer Nichtrest modulo p ist. Dabei muss 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[Bearbeiten]

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 des Moduls 2, modulo 2 gibt es also keine Nichtreste:

L(a,2) = 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}(k) \equiv a \cdot k \pmod p

eine Permutation der Zahlen von 0 bis p-1 darstellt und \operatorname{sgn} das Vorzeichen einer Permutation bezeichnet.

Beispiele[Bearbeiten]

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

Rechenregeln[Bearbeiten]

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

Es seien nun a, b \in \Z und p eine Primzahl. Dann gelten folgende Rechenregeln:

  • a \equiv b \pmod p \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
  • \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right) = \left(\frac{a\cdot b}{p}\right)
  • \sum_{k=1}^{p-1} \left(\frac{k}{p}\right) = 0 für p\ne 2.

Die besondere Stellung der Zahl 3[Bearbeiten]

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]