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.
Das Legendre-Symbol gibt an, ob die Zahl
quadratischer Rest modulo
oder quadratischer Nichtrest modulo
ist. Dabei ist
eine ganze Zahl und
eine ungerade Primzahl.
Es gilt
![{\displaystyle \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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70190ec3e4d08ca7de9310bc52a8b155aa2b8322)
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
und
.
Das eulersche Kriterium gibt eine mögliche Berechnungsmethode zum Legendre-Symbol an:
.
Eine weitere Berechnungsmöglichkeit liefert das Lemma von Zolotareff mit
![{\displaystyle \left({\frac {a}{p}}\right)=\operatorname {sgn} (\pi _{a,p}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7b75b63ccf9a2579e666c6ab375fb662c3d2e04)
wobei
, die durch
![{\displaystyle \pi _{a,p}(k)\equiv a\cdot k{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e9805d78ff8d8b4f948ecd7bcd52532d5599f62)
definierte Permutation der Zahlen von
ist, und
das Vorzeichen einer Permutation bezeichnet.
2 ist quadratischer Rest modulo 7 – in der Tat ist ja
:
![{\displaystyle \left({\frac {2}{7}}\right)\equiv 2^{\frac {7-1}{2}}=2^{3}\equiv 1\mod 7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3d6ed8ea8479994357cd3e5278f7ac6b8775fd1)
5 ist quadratischer Nichtrest modulo 7:
![{\displaystyle \left({\frac {5}{7}}\right)\equiv 5^{\frac {7-1}{2}}=5^{3}\equiv 6\equiv -1\mod 7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f61ae15f410f98d94f91582b380c33806e83532b)
14 ist durch 7 teilbar (also weder Rest noch Nichtrest von 7):
![{\displaystyle \left({\frac {14}{7}}\right)\equiv 14^{\frac {7-1}{2}}=14^{3}\equiv 0\mod 7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac36bd4f0e1ad9a349d894a8c34d7c0b60df5a90)
Das quadratische Reziprozitätsgesetz macht wichtige Aussagen über das Rechnen mit dem Legendre-Symbol.
Außerdem gelten für alle ganze Zahlen
,
und alle Primzahlen
folgende Rechenregeln:
![{\displaystyle a\equiv b{\pmod {p}}\Rightarrow \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f98cdc8e6f0011d0f648d19c9c68b9c24d7ea695)
![{\displaystyle \left({\frac {a}{p}}\right)\cdot \left({\frac {b}{p}}\right)=\left({\frac {a\cdot b}{p}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7460396f7d915f34ddd23e85e81a185140a1e09)
.
Es gilt
![{\displaystyle \left({\frac {1}{p}}\right)=1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed7952a55956def1e1b9a064837ded3ce494c887)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba46c2bd97b30b158077743e5dc2fa2cccc9a7e5)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a6d85a9c12857462ba3a7c7234a16a4059beef0)
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
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13d7aea372c45b82c02ed997a1887e0761870aa2)
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:
![{\displaystyle \left({\frac {a}{3}}\right)\equiv a^{\frac {3-1}{2}}\ \operatorname {mod} \ 3=a\ \operatorname {mod} \ 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91f2ef424e5f518d0ae5f55e9a697308c35d0716)
Andererseits gilt auch:
![{\displaystyle \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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/866dc759fb9e95ee13ec36bdc5413bfc6dde4a70)
Siehe dazu unter Pythagoreische Primzahl.