Symbol Legendre’a

Symbol Legendre’a – funkcja ściśle multiplikatywna stosowana w teorii liczb, oznaczana $(a|p)$ lub $\left({\frac {a}{p}}\right)$ ^[1]^[2]^[3].

Wprowadzony w 1798 przez Legendre’a^[4]. Jego uogólnieniem jest symbol Jacobiego.

Definicja

Niech $p>2$ będzie liczbą pierwszą. Liczbę $a$ niebędącą wielokrotnością $p$ nazwiemy resztą kwadratową modulo $p,$ jeśli istnieje liczba całkowita $t$ taka, że $a\equiv t^{2}{\pmod {p}}.$ Fakt ten oznaczymy $a\mathrm {R} p.$ Jeśli taka liczba $t$ nie istnieje, liczbę $a$ nazywamy nieresztą kwadratową modulo $p$ ^[1], w artykule oznaczamy to jako $a\mathrm {N} p.$ Wielokrotności liczby $p$ nie zaliczamy ani do reszt ani do niereszt^[2].

$\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{gdy }}a\mathrm {R} p,\\-1&{\text{gdy }}a\mathrm {N} p,\\0&{\text{gdy }}a\equiv 0{\pmod {p}}.\end{cases}}$

Czasami za dziedzinę funkcji nie przyjmuje się wielokrotności $p$ ^[1]^[2]^[3].

Własności

Jeśli $a\equiv b{\pmod {p}},$ to $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$ ^[2].
Kryterium Eulera jest użyteczne do obliczania wartości symbolu oraz jest używane do dowodzenia innych własności:
$\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}$ ^[1]^[2]^[3].
Symbol Legendre’a jest funkcją ściśle multiplikatywną licznika: $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).$ Ta własność jest wnioskiem z kryterium Eulera^[1]^[2]^[3].
Najważniejszą własnością jest prawo wzajemności reszt kwadratowych, zwane czasami theorema fundamentale (twierdzenie podstawowe) lub theorema aurerum (twierdzenie złote)^[1]^[2]^[5]:
$p\neq q\Rightarrow \left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.$
Tę własność, będącą wnioskiem z kryterium Eulera, nazywa się I uzupełnieniem prawa wzajemności^[1]^[2]:
$\left({\frac {-1}{p}}\right)={\begin{cases}1&{\text{gdy }}p\equiv 1{\pmod {4}},\\-1&{\text{gdy }}p\equiv 3{\pmod {4}}.\end{cases}}$
Istnieje również II uzupełnienie prawa wzajemności^[1]:
$\left({\frac {2}{p}}\right)={\begin{cases}1&{\text{gdy }}p\equiv \pm 1{\pmod {8}},\\-1&{\text{gdy }}p\equiv \pm 3{\pmod {8}}.\end{cases}}$

Tabela wartości

Tabela przedstawia wartości funkcji dla $a\leqslant 30$ i $3\leqslant p\leqslant 127$ ^[6].

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

Przypisy

↑ ^a ^b ^c ^d ^e ^f ^g ^h AdamA. Neugebauer AdamA., Matematyka olimpijska. 1, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2018, s. 204–211, ISBN 978-83-7267-710-5, OCLC 1055646686 [dostęp 2022-08-14] .
↑ ^a ^b ^c ^d ^e ^f ^g ^h WładysławW. Narkiewicz WładysławW., Teoria liczb, wyd. 3, Warszawa: Wydawnictwo Naukowe PWN, 2003, s. 61, 63–65, 139, 169, ISBN 83-01-14015-1, OCLC 749285993 [dostęp 2022-08-14] .
↑ ^a ^b ^c ^d Eric W.E.W. Weisstein Eric W.E.W., Legendre Symbol [online], mathworld.wolfram.com [dostęp 2022-08-14] (ang.).
↑ A.M. (Adrien Marie)A.M.(A.M.) Legendre A.M. (Adrien Marie)A.M.(A.M.), Essai sur la théorie des nombres, Paris, Duprat, 1798 [dostęp 2022-08-14] .
↑ Eric W.E.W. Weisstein Eric W.E.W., Quadratic Reciprocity Theorem [online], mathworld.wolfram.com [dostęp 2022-08-14] (ang.).
↑ Legendre Symbol(LS) Calculator [online], www.mymathtables.com [dostęp 2022-08-14] .

Linki zewnętrzne

Kalkulator symbolu Legendre’a
Legendre symbol (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].

[:0-1] ↑ ^a ^b ^c ^d ^e ^f ^g ^h AdamA. Neugebauer AdamA., Matematyka olimpijska. 1, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2018, s. 204–211, ISBN 978-83-7267-710-5, OCLC 1055646686 [dostęp 2022-08-14] .

[:1-2] ↑ ^a ^b ^c ^d ^e ^f ^g ^h WładysławW. Narkiewicz WładysławW., Teoria liczb, wyd. 3, Warszawa: Wydawnictwo Naukowe PWN, 2003, s. 61, 63–65, 139, 169, ISBN 83-01-14015-1, OCLC 749285993 [dostęp 2022-08-14] .

[:2-3] Eric W.E.W. Weisstein Eric W.E.W., Legendre Symbol [online], mathworld.wolfram.com [dostęp 2022-08-14] (ang.).

[4] A.M. (Adrien Marie)A.M.(A.M.) Legendre A.M. (Adrien Marie)A.M.(A.M.), Essai sur la théorie des nombres, Paris, Duprat, 1798 [dostęp 2022-08-14] .

[5] Eric W.E.W. Weisstein Eric W.E.W., Quadratic Reciprocity Theorem [online], mathworld.wolfram.com [dostęp 2022-08-14] (ang.).

[6] Legendre Symbol(LS) Calculator [online], www.mymathtables.com [dostęp 2022-08-14] .

[1]

[2]

[3]

[4]

[5]

[6]