## [Auswertung des Legendre-Symbols](/de/node/62923) Definition Die rechnerische Bestimmung des Legendre-Symbols (a|p) für eine ganze Zahl a modulo einer ungeraden Primzahl p, wobei das Ergebnis 1 für quadratische Reste (a ≠ 0 mod p), −1 für Nichtreste und 0 für a ≡ 0 mod p ist. ## Prinzip Prinzip Verwende Multiplikativität und das Eulersche Kriterium: (a|p) ≡ a^{(p−1)/2} (mod p), kombiniert mit quadratischer Reziprozität und Reduktion modulo p, um die Auswertung auf kleinere Residuen und bekannte Fälle zu reduzieren. ## Demonstration Demonstration Beispiel: p = 7, a = 3. Berechne 3^{(7−1)/2}=3^3=27≡6≡−1 (mod 7), also (3|7)=−1; 3 ist ein quadratischer Nichtrest modulo 7. ## Fehlanwendung Fehlanwendung Das Legendre‑Symbol auf zusammengesetzte Moduli anwenden (den Jacobi‑Wert als endgültige Aussage nehmen) oder annehmen, dass (a|p)=1 ohne weitere Prüfung unmittelbar eine konkrete Quadratwurzel liefert. ## Konsequenz Konsequenz Eine korrekte Auswertung entscheidet die Lösbarkeit von x^2≡a (mod p), vereinfacht die Lösung quadratischer Kongruenzen und ist Baustein in Reziprozitätsberechnungen und bei Charakter‑Summen in Zahlentheorie und algebraischer Zahlentheorie. ## Umkehrung Umkehrung Ersetzt man das Legendre‑Symbol durch das Jacobi‑Symbol für ein zusammengesetztes Modul, verliert man die Entschiedenheit: Jacobi=1 garantiert keine Quadratzahlentheorie‑Lösung, was den Gegensatz von Prim‑ und Kompositmodul zeigt. ## Abgrenzung Abgrenzung Gilt nur für ganze Zahlen a und ungerade Primmoduli p (p>2); schließt das Modul 2 und zusammengesetzte Moduli aus, sofern nicht ausdrücklich als Jacobi‑Symbol interpretiert; vorausgesetzt wird Rechnen in Z/pZ mit kanonischen Restklassen. ## Semantische Spannung Semantische Spannung Es besteht Spannung zwischen dem kompakten algebraischen Test (Eulersches Kriterium) und dem allgemeineren, aber weniger entscheidenden Jacobi‑Symbol: beide sind algorithmisch ähnlich, semantisch jedoch unterschiedlich aussagekräftig. ## Synthese Synthese Die Auswertung des Legendre‑Symbols ist ein algorithmisch‑algebraischer Vorgang, der mittels Eulerschem Kriterium, Multiplikativität und Reziprozität die Frage der quadratischen Residuosität modulo einer ungeraden Primzahl auf endliche Potenz‑ und Vorzeichenberechnungen reduziert und deren Anwendungsbereich klärt.