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

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

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

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

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

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

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

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

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.