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 <math>a</math> 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-Symbols, das wiederum eine Spezialisierung des Kronecker-Symbols 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 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 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 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.