Legendární symbol - Legendre symbol

Symbol legendy (A/p)
pro různé A (podél horní části) a p (podél levé strany).
A p	0	1	2	3	4	5	6	7	8	9	10
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
11	−0	−1	−1	1	−1	1	−1	−1	−1	−1	−1
Pouze 0 ≤ A < p jsou zobrazeny, protože kvůli první vlastnosti pod jakoukoli jinou A lze snížit modulo p. Kvadratické zbytky jsou zvýrazněny žlutě a přesně odpovídají hodnotám 0 a 1.

v teorie čísel, Legendární symbol je multiplikativní funkce s hodnotami 1, -1, 0, což je kvadratický znak modulo lichý prvočíslo p: jeho hodnota v (nenulová) kvadratický zbytek modp je 1 a na nekvadratickém zbytku (nezbytky) je -1. Jeho hodnota na nule je 0.

Symbol Legendre představil Adrien-Marie Legendre v roce 1798^[1] v průběhu svých pokusů o prokázání zákon kvadratické vzájemnosti. Zevšeobecnění symbolu zahrnuje Jacobi symbol a Dirichletovy postavy vyššího řádu. Značná výhoda symbolu Legendre inspirovala zavedení několika dalších „symbolů“ používaných v algebraická teorie čísel, tak jako Hilbertův symbol a Artin symbol.

Definice

Nechat ${displaystyle p}$ být lichý prvočíslo. Celé číslo ${displaystyle a}$ je kvadratický zbytek modulo ${displaystyle p}$ Pokud to je shodný do a perfektní čtverec modulo ${displaystyle p}$ a je kvadratickým neresiduálním modulem ${displaystyle p}$ v opačném případě. The Legendární symbol je funkce ${displaystyle a}$ a ${displaystyle p}$ definováno jako

{displaystyle left ({frac {a} {p}} ight) = {egin {cases} 1 & {ext {if}} a {ext {is a quadratic remain modulo}} p {ext {and}} aot equiv 0 { pmod {p}}, - 1 & {ext {if}} a {ext {je nekvadratický zbytek modulo}} p, 0 & {ext {if}} aequiv 0 {pmod {p}}. end {případy }}}

Legendrova původní definice byla pomocí explicitního vzorce

{displaystyle left ({frac {a} {p}} ight) equiv a ^ {frac {p-1} {2}} {pmod {p}} quad {ext {and}} quad left ({frac {a} {p}} ight) za {-1,0,1}.}

Podle Eulerovo kritérium, který byl objeven dříve a byl známý Legendrovi, jsou tyto dvě definice rovnocenné.^[2] Příspěvek Legendre tedy spočíval v zavedení pohodlného notace který zaznamenal kvadratickou reziduozitu A modp. Pro srovnání Gauss použil notaci ARp, ANp podle toho, zda A je zbytek nebo ne-zbytek modulo p. Z důvodu typografického pohodlí je symbol Legendre někdy psán jako (A | p) nebo (A/p). Sekvence (A | p) pro A rovno 0, 1, 2, ... je periodicky s tečkou p a někdy se mu říká Legendární sekvence, přičemž hodnoty {0,1, −1} jsou občas nahrazeny hodnotami {1,0,1} nebo {0,1,0}.^[3] U každého řádku v následující tabulce je vidět, že vykazuje periodicitu, jak je popsáno.

Tabulka hodnot

Následuje tabulka hodnot symbolu Legendre ${displaystyle left ({frac {a} {p}} ight)}$ s p ≤ 127, A ≤ 30, p lichý prime.

A p	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
3	−1	−1	0	−1	−1	0	1	−1	−0	1	−1	0	1	−1	0	−1	−1	0	1	−1	0	1	−1	0	−1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
41	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1
61	1	−1	1	1	1	−1	−1	−1	1	−1	−1	1	1	1	1	1	−1	−1	1	1	−1	1	−1	−1	1	−1	1	−1	−1	−1
67	1	−1	−1	1	−1	1	−1	−1	1	1	−1	−1	−1	1	1	1	1	−1	1	−1	1	1	1	1	1	1	−1	−1	1	−1
71	1	1	1	1	1	1	−1	1	1	1	−1	1	−1	−1	1	1	−1	1	1	1	−1	−1	−1	1	1	−1	1	−1	1	1
73	1	1	1	1	−1	1	−1	1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	−1	−1	−1	1	1	1	−1	1	−1	−1	−1
79	1	1	−1	1	1	−1	−1	1	1	1	1	−1	1	−1	−1	1	−1	1	1	1	1	1	1	−1	1	1	−1	−1	−1	−1
83	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	1	1	1
89	1	1	−1	1	1	−1	−1	1	1	1	1	−1	−1	−1	−1	1	1	1	−1	1	1	1	−1	−1	1	−1	−1	−1	−1	−1
97	1	1	1	1	−1	1	−1	1	1	−1	1	1	−1	−1	−1	1	−1	1	−1	−1	−1	1	−1	1	1	−1	1	−1	−1	−1
101	1	−1	−1	1	1	1	−1	−1	1	−1	−1	−1	1	1	−1	1	1	−1	1	1	1	1	1	1	1	−1	−1	−1	−1	1
103	1	1	−1	1	−1	−1	1	1	1	−1	−1	−1	1	1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	−1	1	1	1
107	1	−1	1	1	−1	−1	−1	−1	1	1	1	1	1	1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	−1	1	−1	1	1
109	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	−1	−1	−1	1	1	1	−1	−1	1	1	1	1	1	−1
113	1	1	−1	1	−1	−1	1	1	1	−1	1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	1	−1	1	−1	1
127	1	1	−1	1	−1	−1	−1	1	1	−1	1	−1	1	−1	1	1	1	1	1	−1	1	1	−1	−1	1	1	−1	−1	−1	1

Vlastnosti symbolu Legendre

Existuje celá řada užitečných vlastností symbolu Legendre, které spolu s právem kvadratická vzájemnost, lze použít k efektivnímu výpočtu.

Symbol Legendre odhaluje paritu nenulového celočíselného módu p. To znamená daný generátor ${displaystyle gin mathbb {F} _ {p} ^ {*}}$ , pokud ${displaystyle x = g ^ {r}}$ pak ${displaystyle x}$ je kvadratický zbytek právě tehdy ${displaystyle r}$ je sudý. To také ukazuje, že polovina nenulových prvků v ${displaystyle mathbb {F} _ {p} ^ {*}}$ jsou kvadratické zbytky.
Li ${displaystyle pequiv 3 {ext {mod}} 4}$ pak skutečnost, že
${displaystyle {frac {p + 1} {4}} + {frac {p + 1} {4}} = {frac {(p-1) +2} {2}}}$ nám to dává ${displaystyle a = x ^ {(p + 1) / 4}}$ je druhá odmocnina kvadratického zbytku ${displaystyle x}$ .
Symbol Legendre je ve svém prvním (nebo horním) argumentu periodický: if A ≡ b (mod p), pak
${displaystyle left ({frac {a} {p}} ight) = left ({frac {b} {p}} ight).}$
Symbol Legendre je a zcela multiplikativní funkce jeho top argumentu:
${displaystyle left ({frac {ab} {p}} ight) = left ({frac {a} {p}} ight) left ({frac {b} {p}} ight).}$
Zejména produkt dvou čísel, která jsou kvadratickými zbytky nebo kvadratickými nezbytky modulo p je zbytek, zatímco produkt zbytku se zbytkem je zbytek. Zvláštním případem je symbol legendy čtverce:
${displaystyle left ({frac {x ^ {2}} {p}} ight) = {egin {cases} 1 & {mbox {if}} pmid x 0 & {mbox {if}} pmid x.end {cases}} }$
Při pohledu na funkci A, symbol Legendre ${displaystyle left ({frac {a} {p}} ight)}$ je jedinečný kvadratický (nebo řád 2) Dirichletova postava modulo p.
První dodatek k zákonu kvadratické vzájemnosti:
${displaystyle left ({frac {-1} {p}} ight) = (- 1) ^ {frac {p-1} {2}} = {egin {cases} 1 & {mbox {if}} pequiv 1 {pmod {4}} - 1 & {mbox {if}} pequiv 3 {pmod {4}}. End {cases}}}$
Druhý dodatek k zákonu kvadratické vzájemnosti:
${displaystyle left ({frac {2} {p}} ight) = (- 1) ^ {frac {p ^ {2} -1} {8}} = {egin {cases} 1 & {mbox {if}} pequiv 1 {mbox {or}} 7 {pmod {8}} - 1 & {mbox {if}} pequiv 3 {mbox {or}} 5 {pmod {8}}. End {cases}}}$
Speciální vzorce pro symbol Legendre ${displaystyle left ({frac {a} {p}} ight)}$ ${displaystyle left ({frac {a} {p}} ight)}$ pro malé hodnoty A:
- Pro liché prvočíslo p ≠ 3,
  ${displaystyle left ({frac {3} {p}} ight) = (- 1) ^ {{ig lfloor} {frac {p + 1} {6}} {ig floor}} = {egin {cases} 1 & { mbox {if}} pequiv 1 {mbox {or}} 11 {pmod {12}} - 1 & {mbox {if}} pequiv 5 {mbox {or}} 7 {pmod {12}}. end {cases}} }$
- Pro liché prvočíslo p ≠ 5,
  ${displaystyle left ({frac {5} {p}} ight) = (- 1) ^ {{ig lfloor} {frac {2p + 2} {5}} {ig floor}} = {egin {cases} 1 & { mbox {if}} pequiv 1 {mbox {or}} 4 {pmod {5}} - 1 & {mbox {if}} pequiv 2 {mbox {or}} 3 {pmod {5}}. end {cases}} }$
The Fibonacciho čísla 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… jsou definovány opakováním F₁ = F₂ = 1, F_n+1 = F_n + F_n−1. Li p je tedy prvočíslo
${displaystyle F_ {p-left ({frac {p} {5}} ight)} equiv 0 {pmod {p}}, qquad F_ {p} equiv left ({frac {p} {5}} ight) {pmod {p}}.}$

Například,

{displaystyle {egin {aligned} left ({frac {2} {5}} ight) & = - 1, & F_ {3} & = 2, & F_ {2} & = 1, left ({frac {3} { 5}} ight) & = - 1, & F_ {4} & = 3, & F_ {3} & = 2, left ({frac {5} {5}} ight) & = 0, & F_ {5} & = 5, && left ({frac {7} {5}} ight) & = - 1, & F_ {8} & = 21, & F_ {7} & = 13, left ({frac {11} {5}} ight) & = 1, & F_ {10} & = 55, & F_ {11} & = 89.end {zarovnáno}}}

Tento výsledek vychází z teorie Lucasovy sekvence, které se používají v testování primality.^[4] Vidět Zeď – Slunce – Slunce.

Symbol legendy a kvadratická vzájemnost

Nechat p a q být odlišné liché prvočísla. Pomocí symbolu Legendre se symbol kvadratická vzájemnost zákon lze stručně konstatovat:

{displaystyle left ({frac {q} {p}} ight) left ({frac {p} {q}} ight) = (- 1) ^ {{frac {p-1} {2}} cdot {frac { q-1} {2}}}.}

Mnoho důkazy kvadratické vzájemnosti jsou založeny na Legendrově vzorci

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

Kromě toho bylo navrženo několik alternativních výrazů pro symbol Legendre, aby se dosáhlo různých důkazů kvadratického zákona o vzájemnosti.

Gauss představil kvadratická Gaussova suma a použil vzorec

{displaystyle sum _ {k = 0} ^ {p-1} zeta ^ {ak ^ {2}} = left ({frac {a} {p}} ight) sum _ {k = 0} ^ {p-1 } zeta ^ {k ^ {2}}, qquad zeta = e ^ {frac {2pi i} {p}}}

ve své čtvrté^[5] a šestý^[6] důkazy kvadratické vzájemnosti.

Kronecker důkaz^[7] nejprve to stanoví

{displaystyle left ({frac {p} {q}} ight) = operatorname {sgn} left (prod _ {i = 1} ^ {frac {q-1} {2}} prod _ {k = 1} ^ { frac {p-1} {2}} vlevo ({frac {k} {p}} - {frac {i} {q}} ight) ight).}

Obrácení rolí p a q, získá vztah mezi (p/q) a (q/p).

Jeden z Eisenstein důkazy^[8] začíná tím, že ukazuje

{displaystyle left ({frac {q} {p}} ight) = prod _ {n = 1} ^ {frac {p-1} {2}} {frac {sin left ({frac {2pi qn} {p} } ight)} {sin left ({frac {2pi n} {p}} ight)}}}

Použití jisté eliptické funkce místo sinusová funkce, Eisenstein dokázal krychlový a kvartální vzájemnost také.

Související funkce

The Jacobi symbol (A/n) je zobecněním symbolu Legendre, který umožňuje složený druhý (dolní) argument n, Ačkoli n musí být stále liché a pozitivní. Tato generalizace poskytuje efektivní způsob výpočtu všech symbolů Legendre bez provádění faktorizace.
Dalším rozšířením je Symbol Kronecker, ve kterém může být argumentem dolní celé číslo.
The symbol zbytkové síly (A/n)_n zobecňuje symbol Legendre na vyšší sílu n. Symbol Legendre představuje symbol zbytkové síly pro n = 2.

Výpočetní příklad

Výše uvedené vlastnosti, včetně zákona kvadratické reciprocity, lze použít k vyhodnocení libovolného symbolu Legendre. Například:

{displaystyle {egin {aligned} left ({frac {12345} {331}} ight) & = left ({frac {3} {331}} ight) left ({frac {5} {331}} ight) left ( {frac {823} {331}} ight) & = left ({frac {3} {331}} ight) left ({frac {5} {331}} ight) left ({frac {161} {331} } ight) & = left ({frac {3} {331}} ight) left ({frac {5} {331}} ight) left ({frac {7} {331}} ight) left ({frac { 23} {331}} ight) & = (- 1) vlevo ({frac {331} {3}} ight) vlevo ({frac {331} {5}} ight) (- 1) vlevo ({frac { 331} {7}} ight) (- 1) left ({frac {331} {23}} ight) & = - left ({frac {1} {3}} ight) left ({frac {1} { 5}} ight) left ({frac {2} {7}} ight) left ({frac {9} {23}} ight) & = - left ({frac {1} {3}} ight) left ( {frac {1} {5}} ight) left ({frac {2} {7}} ight) left ({frac {3 ^ {2}} {23}} ight) & = - (1) (1 ) (1) (1) & = - 1. konec {zarovnáno}}}

Nebo pomocí efektivnějšího výpočtu:

{displaystyle left ({frac {12345} {331}} ight) = left ({frac {98} {331}} ight) = left ({frac {2cdot 7 ^ {2}} {331}} ight) = left ({frac {2} {331}} ight) = (- 1) ^ {frac {331 ^ {2} -1} {8}} = - 1.}

Článek Jacobi symbol má více příkladů manipulace se symboly Legendre.

Poznámky

^ Legendre, A. M. (1798). Essai sur la théorie des nombres. Paříž. p.186.
^ Hardy & Wright, Thm. 83.
^ Kim, Jeong-Heon; Song, Hong-Yeop (2001). "Stopová reprezentace legendárních sekvencí". Designy, kódy a kryptografie. 24: 343–348.
^ Ribenboim, str. 64; Lemmermeyer, ex. 2,25–2,28, s. 73–74.
^ Gauss, „Summierung gewisser Reihen von besonderer Art“ (1811), přetištěno v Untersuchungen ... 463–495
^ Gauss, „Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten“ (1818) přetištěno v Untersuchungen ... 501–505
^ Lemmermeyer, ex. p. 31, 1,34
^ Lemmermeyer, str. 236 a násl.

Reference

Gauss, Carl Friedrich; Maser, H. (překladatel do němčiny) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae a další články o teorii čísel) (druhé vydání), New York: Chelsea, ISBN 0-8284-0191-8
Gauss, Carl Friedrich; Clarke, Arthur A. (překladatel do angličtiny) (1986), Disquisitiones Arithmeticae (druhé, opravené vydání), New York: Springer, ISBN 0-387-96254-9
Bach, Eric; Shallit, Jeffrey (1996), Algoritmická teorie čísel (svazek I: Efektivní algoritmy), Cambridge: MIT Press, ISBN 0-262-02405-5
Hardy, G. H.; Wright, E. M. (1980), Úvod do teorie čísel (páté vydání), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
Irsko, Kenneth; Rosen, Michael (1990), Klasický úvod do moderní teorie čísel (druhé vydání), New York: Springer, ISBN 0-387-97329-X
Lemmermeyer, Franz (2000), Zákony o vzájemnosti: od Eulera po Eisenstein, Berlín: Springer, ISBN 3-540-66957-4
Ribenboim, Paulo (1996), Nová kniha rekordů prvočísel, New York: Springer, ISBN 0-387-94457-5

externí odkazy

Jacobi symbol kalkulačka

[1] Legendre, A. M. (1798). Essai sur la théorie des nombres. Paříž. p.186.

[2] Hardy & Wright, Thm. 83.

[KimSong01-3] Kim, Jeong-Heon; Song, Hong-Yeop (2001). "Stopová reprezentace legendárních sekvencí". Designy, kódy a kryptografie. 24: 343–348.

[4] Ribenboim, str. 64; Lemmermeyer, ex. 2,25–2,28, s. 73–74.

[5] Gauss, „Summierung gewisser Reihen von besonderer Art“ (1811), přetištěno v Untersuchungen ... 463–495

[6] Gauss, „Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten“ (1818) přetištěno v Untersuchungen ... 501–505

[7] Lemmermeyer, ex. p. 31, 1,34

[8] Lemmermeyer, str. 236 a násl.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]