In der Zahlentheorie ist das Symbol von Legendre eine Multiplicative-Funktion mit Werten 1, −1, 0, der ein quadratischer Charakter modulo eine Primzahl p ist: Sein Wert auf einem quadratischen (nichtnull)-Rückstand mod p ist 1, und auf einem quadratischen Nichtrückstand ist −1.

Das Symbol von Legendre wurde von Adrien-Marie Legendre 1798 im Laufe seiner Versuche des Beweises des Gesetzes der quadratischen Reziprozität eingeführt. Generalisationen des Symbols schließen das Symbol von Jacobi und die Charaktere von Dirichlet der höheren Ordnung ein. Die notational Bequemlichkeit des Symbols von Legendre hat Einführung von mehreren anderen "Symbolen" begeistert, die in der Theorie der algebraischen Zahl, wie das Symbol von Hilbert und das Symbol von Artin verwendet sind.

Definition

Lassen Sie p eine sonderbare Primzahl sein. Eine ganze Zahl eines quadratischen Rückstands modulo p zu sein, wenn es zu einem vollkommenen Quadrat modulo p kongruent ist und ein quadratischer Nichtrückstand modulo p sonst ist. Das Legendre Symbol ist eine Funktion von a und p definiert wie folgt:

:

\left (\frac {p }\\Recht) =

\begin {Fälle }\

\; \; \, 1 \text {wenn} ein \text {ein quadratischer Rückstand modulo }\\p ist

\text {und} ein \not\equiv 0\pmod {p} \\

- 1 \text {wenn} ein \text {ein quadratischer Nichtrückstand modulo }\\p \\ist

\; \; \, 0 \text {wenn} ein \equiv 0 \pmod {p}.

\end {Fälle }\

</Mathematik>

Die ursprüngliche Definition von Legendre war mittels einer ausführlichen Formel:

:

Durch das Kriterium von Euler, das früher entdeckt worden war und Legendre bekannt war, sind diese zwei Definitionen gleichwertig. So legt der Beitrag von Legendre das Einführen einer günstigen Notation an, die quadratischen residuosity eines mod p registriert hat. Wegen des Vergleichs hat Gauss die Notation, gemäß ob verwendet eines Rückstands oder eines Nichtrückstands modulo p zu sein.

Für die typografische Bequemlichkeit wird das Symbol von Legendre manchmal als (AFP) oder (a/p) geschrieben. Die Folge (AFP) für einen gleichen 0,1,2, ist... mit der Periode p periodisch und wird manchmal die Folge von Legendre, mit {0,1, 1} Werte genannt, die gelegentlich durch {1,0,1} oder {0,1,0} ersetzt sind.

Eigenschaften des Symbols von Legendre

Es gibt mehrere nützliche Eigenschaften des Symbols von Legendre, das, zusammen mit dem Gesetz der quadratischen Reziprozität, verwendet werden kann, um es effizient zu schätzen.

• Das Legendre Symbol ist in seinem ersten (oder Spitze) Argument periodisch: wenn ein  b (mod p), dann

::

\left (\frac {p }\\Recht) = \left (\frac {b} {p }\\Recht).

</Mathematik>

• Das Legendre Symbol ist völlig multiplicative Funktion seines Spitzenarguments:

::

\left (\frac {ab} {p }\\Recht) = \left (\frac {p }\\Recht) \left (\frac {b} {p }\\Recht).

</Mathematik>

: Insbesondere das Produkt von zwei Zahlen, die beide quadratische Rückstände oder quadratische Nichtrückstände modulo p sind, ist ein Rückstand, wohingegen das Produkt eines Rückstands mit einem Nichtrückstand ein Nichtrückstand ist. Ein spezieller Fall ist das Symbol von Legendre eines Quadrats:

::

\left (\frac {x^2} {p }\\Recht) =

\begin {Fälle} 1& \mbox {wenn} p\nmid x \\0& \mbox {wenn} p\mid x.

\end {Fälle }\</Mathematik>

• Wenn angesehen, als eine Funktion von a ist das Symbol von Legendre das einzigartige quadratische (oder Auftrag 2) Charakter von Dirichlet modulo p.
• Die erste Ergänzung des Gesetzes der quadratischen Reziprozität:

::

\left (\frac {-1} {p }\\Recht)

(-1) ^\\tfrac {p-1} {2 }\

\begin {Fälle }\

\; \; \, 1\mbox {wenn} p \equiv 1\pmod {4} \\

- 1\mbox {wenn} p \equiv 3\pmod {4}. \end {Fälle} </Mathematik>

• Die zweite Ergänzung des Gesetzes der quadratischen Reziprozität:

::

\left (\frac {2} {p }\\Recht)

(-1) ^\\tfrac {p^2-1} {8 }\

\begin {Fälle }\

\; \; \, 1\mbox {wenn} p \equiv 1\mbox {oder} 7 \pmod {8} \\

- 1\mbox {wenn} p \equiv 3\mbox {oder} 5 \pmod {8}. \end {Fälle} </Mathematik>

• Spezielle Formeln für das Symbol von Legendre für kleine Werte von a:

:* Für einen sonderbaren ersten p  3,

::

\left (\frac {3} {p }\\Recht)

(-1) ^ {\\big\lfloor \frac {p+1} {6 }\\big\rfloor }\

\begin {Fälle }\

\; \; \, 1\mbox {wenn} p \equiv 1\mbox {oder} 11 \pmod {12} \\

- 1\mbox {wenn} p \equiv 5\mbox {oder} 7 \pmod {12}. \end {Fälle} </Mathematik>

:* Für einen sonderbaren ersten p  5,

::

\left (\frac {5} {p }\\Recht)

(-1) ^ {\\big\lfloor \frac {p+2} {5 }\\großer \rfloor }\

\begin {Fälle }\

\; \; \, 1\mbox {wenn} p \equiv 1\mbox {oder} 4 \pmod5 \\

- 1\mbox {wenn} p \equiv 2\mbox {oder} 3 \pmod5. \end {Fälle} </Mathematik>

• Die Fibonacci-Zahlen 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, werden... durch das Wiederauftreten definiert, Wenn p eine Primzahl dann ist

:

F_ {p-\left (\frac {p} {5 }\\Recht)} \equiv 0 \pmod p, \; \; \;

F_ {p} \equiv \left (\frac {p} {5 }\\Recht) \pmod p.

</Mathematik>

Zum Beispiel,

:\begin {richten }\aus

& (\tfrac {2} {5}) &= &-1, &F_3 &= 2, \; \; \; \;&F_2 &=1, \\

& (\tfrac {3} {5}) &= &-1, &F_4 &= 3,&F_3&=2, \\

& (\tfrac {5} {5}) &= &\\; \; \; \; 0, &F_5 &= 5, \\

& (\tfrac {7} {5}) &= &-1, &F_8 &= 21,&F_7&=13, \\

& (\tfrac {11} {5}) &= &\\; \; \, 1, &F_ {10} &= 55, &F_ {11}

&=89. \end {richten }\aus</Mathematik>

Dieses Ergebnis kommt aus der Theorie von Folgen von Lucas, die in der Primality-Prüfung verwendet werden. Sieh ersten Sonne-Sonne des Wand-.

Symbol von Legendre und quadratische Reziprozität

Lassen Sie p und q sonderbare Blüte sein. Mit dem Symbol von Legendre kann das quadratische Reziprozitätsgesetz kurz festgesetzt werden:

:

\left (\frac {q} {p }\\Recht)

\left (\frac {p} {q }\\Recht) (-1) ^ {\\tfrac {p-1} {2 }\\tfrac {q-1} {2}}.

</Mathematik>

Viele Beweise der quadratischen Reziprozität basieren auf der Formel von Legendre

:

\left (\frac {p }\\Recht) \equiv a^ {\\tfrac {p-1} {2} }\\pmod p.

</Mathematik>

Außerdem wurden mehrere alternative Ausdrücke für das Symbol von Legendre ausgedacht, um verschiedene Beweise des quadratischen Reziprozitätsgesetzes zu erzeugen.

• Gauss hat die quadratische Summe von Gauss eingeführt und hat die Formel verwendet

::

\sum_ {k=0} ^ {p-1 }\\zeta^ {ak^2} =

\left (\frac {p }\\Recht) \sum_ {k=0} ^ {p-1 }\\zeta^ {k^2},

\quad \zeta = e^ {2\pi i/p }\

</Mathematik>

:in seine vierten und sechsten Beweise der quadratischen Reziprozität.

• Der Beweis von Kronecker gründet zuerst das

::

\left (\frac {p} {q }\\Recht)

\sgn\left (\prod_ {ich

1\ist ^ {\\frac {q-1} {2} }\\prod_ {k=1} ^ {\\frac {p-1} {2} }\\(\frac {k} {p}-\frac {ich} {q }\\Recht) \right) abgereist. </Mathematik>

: Die Rollen von p und q umkehrend, erhält er die Beziehung zwischen und

den

• Einer der Beweise von Eisenstein beginnt durch die Vertretung dem

von::

\left (\frac {q} {p }\\Recht)

\prod_ {n

1\^ {\\frac {p-1} {2}} \frac {\\Sünde (\frac {2\pi qn} {p})} {\\Sünde (\frac {2\pi n} {p})}.

</Mathematik>

: Mit bestimmten elliptischen Funktionen statt der Sinusfunktion ist Eisenstein im Stande gewesen, kubische und quartic Reziprozität ebenso zu beweisen.

Zusammenhängende Funktionen

• Das Jacobi Symbol ist eine Generalisation des Symbols von Legendre, das eine zerlegbare Sekunde (Boden) Argument n berücksichtigt, obwohl n noch seltsam und positiv sein muss. Diese Generalisation stellt eine effiziente Weise zur Verfügung, alle Symbole von Legendre zu schätzen, ohne factorization entlang dem Weg durchzuführen.
• Eine weitere Erweiterung ist das Symbol von Kronecker, in dem das unterste Argument jede ganze Zahl sein kann.

Rechenbetontes Beispiel

Die obengenannten Eigenschaften, einschließlich des Gesetzes der quadratischen Reziprozität, können verwendet werden, um jedes Symbol von Legendre zu bewerten. Zum Beispiel:

::::::::

Oder das Verwenden einer effizienteren Berechnung:

:

Das Symbol des Artikels Jacobi hat mehr Beispiele der Symbol-Manipulation von Legendre.

Referenzen

Außenverbindungen

• Symbol-Rechenmaschine von Jacobi