Das Legendre Symbol ist eine Kurzschreibweise die in der Zahlentheorie einem Teilgebiet der Mathematik verwendet wird Es ist nach dem franzosischen Mathematiker Adrien Marie Legendre benannt Inhaltsverzeichnis 1 Definition und Notation 2 Berechnung 3 Beispiele 4 Rechenregeln 5 Spezielle Werte 6 Die besondere Stellung der Zahl 3 7 Besonderheiten bei PrimzahlenDefinition und Notation BearbeitenDas Legendre Symbol gibt an ob die Zahl a displaystyle a nbsp quadratischer Rest modulo p displaystyle p nbsp oder quadratischer Nichtrest modulo p displaystyle p nbsp ist Dabei ist a displaystyle a nbsp eine ganze Zahl und p displaystyle p nbsp eine ungerade Primzahl Es gilt a p 1 wenn a quadratischer Rest modulo p ist 1 wenn a quadratischer Nichtrest modulo p ist 0 wenn a ein Vielfaches von p ist displaystyle left frac a p right begin cases 1 amp mbox wenn a mbox quadratischer Rest modulo p mbox ist 1 amp mbox wenn a mbox quadratischer Nichtrest modulo p mbox ist 0 amp mbox wenn a mbox ein Vielfaches von p mbox ist end cases nbsp Das Legendre Symbol ist ein Spezialisierung des Jacobi Symbols das wiederum eine Spezialisierung des Kronecker Symbols ist Alle drei Symbole benutzen daher unmissverstandlich dieselbe Schreibweise Weitere Notationsvarianten fur das Legendre Symbol sind a p displaystyle a p nbsp und L a p displaystyle L a p nbsp Berechnung BearbeitenDas eulersche Kriterium gibt eine mogliche Berechnungsmethode zum Legendre Symbol an a p a p 1 2 mod p displaystyle left frac a p right equiv a frac p 1 2 pmod p nbsp Eine weitere Berechnungsmoglichkeit liefert das Lemma von Zolotareff mit a p sgn p a p displaystyle left frac a p right operatorname sgn pi a p nbsp wobei p a p displaystyle pi a p nbsp die durch p a p k a k mod p displaystyle pi a p k equiv a cdot k pmod p nbsp definierte Permutation der Zahlen von k 0 p 1 displaystyle k 0 dotsc p 1 nbsp ist und sgn displaystyle operatorname sgn nbsp das Vorzeichen einer Permutation bezeichnet Beispiele Bearbeiten2 ist quadratischer Rest modulo 7 in der Tat ist ja 2 3 2 mod 7 displaystyle 2 equiv 3 2 pmod 7 nbsp 2 7 2 7 1 2 2 3 1 mod 7 displaystyle left frac 2 7 right equiv 2 frac 7 1 2 2 3 equiv 1 mod 7 nbsp 5 ist quadratischer Nichtrest modulo 7 5 7 5 7 1 2 5 3 6 1 mod 7 displaystyle left frac 5 7 right equiv 5 frac 7 1 2 5 3 equiv 6 equiv 1 mod 7 nbsp 14 ist durch 7 teilbar also weder Rest noch Nichtrest von 7 14 7 14 7 1 2 14 3 0 mod 7 displaystyle left frac 14 7 right equiv 14 frac 7 1 2 14 3 equiv 0 mod 7 nbsp Rechenregeln BearbeitenDas quadratische Reziprozitatsgesetz macht wichtige Aussagen uber das Rechnen mit dem Legendre Symbol Ausserdem gelten fur alle ganze Zahlen a displaystyle a nbsp b displaystyle b nbsp und alle Primzahlen p displaystyle p nbsp folgende Rechenregeln a b mod p a p b p displaystyle a equiv b pmod p Rightarrow left frac a p right left frac b p right nbsp a p b p a b p displaystyle left frac a p right cdot left frac b p right left frac a cdot b p right nbsp k 1 p 1 k p 0 displaystyle sum k 1 p 1 left frac k p right 0 nbsp Spezielle Werte BearbeitenEs gilt 1 p 1 displaystyle left frac 1 p right 1 nbsp 2 p 1 p 2 1 8 1 fur p 1 oder 7 mod 8 1 fur p 3 oder 5 mod 8 displaystyle left frac 2 p right 1 frac p 2 1 8 begin cases 1 amp mbox fur p equiv 1 mbox oder 7 pmod 8 1 amp mbox fur p equiv 3 mbox oder 5 pmod 8 end cases nbsp 1 p 1 p 1 2 1 fur p 1 mod 4 1 fur p 3 mod 4 displaystyle left frac 1 p right 1 frac p 1 2 begin cases 1 amp mbox fur p equiv 1 pmod 4 1 amp mbox fur p equiv 3 pmod 4 end cases nbsp Diese speziellen Werte reichen aus um jedes nicht verschwindende Legendre Symbol durch wiederholtes Aufteilen des Zahlers in Primfaktoren Anwenden des quadratischen Reziprozitatsgesetzes und modulo Reduktion zu berechnen So ist zum Beispiel 10 31 2 31 5 31 1 1 5 1 2 31 1 2 31 5 1 5 1 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 nbsp Die besondere Stellung der Zahl 3 BearbeitenDie Zahl 3 liefert bei der Ganzzahldivision als Modulo die Werte 0 1 und 1 zuruck Dies entspricht genau den Werten des Legendre Symbols Es gilt also a 3 a 3 1 2 mod 3 a mod 3 displaystyle left frac a 3 right equiv a frac 3 1 2 operatorname mod 3 a operatorname mod 3 nbsp Andererseits gilt auch 3 p l 1 p 1 2 3 4 sin 2 2 p l p 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 nbsp Besonderheiten bei Primzahlen BearbeitenSiehe dazu unter Pythagoreische Primzahl Abgerufen von https de wikipedia org w index php title Legendre Symbol amp oldid 216966408
