WikiDer > Legendre-Symbol

Es Legendre-Symbol oder quadratisches Zeichen ist ein Funktion, die 1798 eingeführt wurde^[1] durch Adrien-Marie Legendre während seines teilweise erfolgreichen Versuchs, das Gesetz der quadratische Gegenseitigkeit zu beweisen.^[2] Das Legendre-Symbol diente mehreren als Prototyp^[3] Restsymbole mit höherer Potenz; andere Erweiterungen und Verallgemeinerungen sind die Jacobi-Symbol, es Kronecker-Symbol, es Hilbert-Symbol und der Artin-Symbol. Es ist eines der ersten Beispiele für a Homomorphismus.^[4]

Definition

Das Legendre-Symbol ${displaystyle({ frac {a}{p}})}$ (in Übereinstimmung mit typografischen Konventionen manchmal geschrieben als (a|p) ) wird für ganze Zahlenein und positivseltsamPrimzahlenp definiert von:

${displaystyle left({frac {a}{p}}ight)={ egin{cases};;,0{mbox{ if }}aequiv 0{pmod {p}}/ 1{mbox{ if }}aot equiv 0 {pmod {p}}{mbox{ und für bestimmte ganze Zahlen }}x,;x^{2}equiv ;a{pmod {p}}/-1{mbox{ falls solche }}x{mbox{ nicht existiert . }}Ende{Fälle}}}$

wenn (ein|p) = 1, dann wird ein ein quadratischer Rest genannt (mod p); wenn (ein|p) = −1, dann wird ein ein quadratisch nicht rückstandsfrei (modp).
Es ist üblich, Null als Sonderfall zu behandeln.

Gauss benutzte die Notation ${displaystyle amarm {R} p}$, ${displaystyle amarm {N} p}$ je nachdem ob ein ein Rest oder ein Nicht-Rest von p ist.

Das periodische Reihe (ein|p) vor dem ein gleich 0,1,2,... wird manchmal zum Legendre-Reihe aufgerufen, wobei die {0.1,-1}-Werte manchmal durch {1,0,1} bzw. {0,1,0} dargestellt werden.^[5]

Elementare Eigenschaften

Das Legendre-Symbol ist periodisch mit Periode p, und hängt somit nur von der Restklasse von ein modular s.

Die quadratischen Residuen modulo p konstituieren Untergruppe mit Index 2 in der Multiplikationsgruppe ${displaystyle mathbb {Z} /pmathbb {Z} ^{*}}$. Also der Restklassen modulo p die nicht die Nullklasse sind, ist genau ein halbes Quadrat.

Eulers Kriterium Cri

Es Eulersches Kriterium^[6] ermöglicht eine direkte Berechnung des Legendre-Symbols:

${displaystyle left({ frac {a}{p}}ight)equiv a^{frac {p-1}{2}}{pmod {p}}}$

In Worten ausgedrückt: wenn p eine ungerade Primzahl ist und ein kein Vielfaches von p, dann ist ein ein quadratischer Rest modulo p dann und nur dann, wenn ein^(p-1)/2-1 ist ein Vielfaches von p, und ein quadratisches Nicht-Rest-Modulo p dann und nur dann, wenn ein^(p-1)/2 1 ist ein Vielfaches von s.

Beispiel

Um herauszufinden, ob 8 mit einem Quadrat modulo 17 kongruent ist, können wir alle Quadrate modulo 17 berechnen, um herauszufinden, dass

${Displaystil 12^{2}=144Äquiv. 8.}$

Wir können jedoch auch das Euler-Kriterium verwenden und überprüfen, dass

${displaystyle 8^{frac {17-1}{2}}=8^{8}=64^{4}Äquiv. 13^{4}=169^{2}Äquiv. (-1)^{2}=1 .}$

Verwandte Funktionen

• Es Jacobi-Symbol ist eine Verallgemeinerung des Legendre-Symbols. Welche Verbindung niedrigsten Zahlen, obwohl die niedrigste Zahl immer noch ungerade und positiv sein muss. Diese Verallgemeinerung bietet eine effektive Methode zur Berechnung aller Legendre-Symbole.
• Es ist eine weitere Verallgemeinerung Kronecker-Symbol die die niedrigsten Zahlen auf alle ganzen Zahlen erweitert.

Fußnoten