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].

Teoria liczb

ogólne typy liczb

naturalne
całkowite
- parzyste i nieparzyste
wymierne
- ułamki egipskie
rzeczywiste
- dodatnie i ujemne
- niewymierne

relacje

podzielność	dzielnik i wielokrotność cechy podzielności
zdefiniowane podzielnością	czynnik pierwszy względna pierwszość kongruencje liczby towarzyskie zaprzyjaźnione

działania

największy wspólny dzielnik (NWD)
- algorytm Euklidesa
najmniejsza wspólna wielokrotność (NWW)
symbol Legendre’a
symbol Jacobiego

liczby pierwsze

podstawy	lemat Euklidesa liczby złożone
testy pierwszości	AKS APR cyklotomiczny ECPP Fermata Lucasa-Lehmera Millera-Rabina Solovaya-Strassena certyfikat pierwszości
sita	Eratostenesa Atkina
faktoryzacja	zasadnicze twierdzenie arytmetyki algorytmy Fermata rho Pollarda Shora GNFS metoda sita liczbowego sito kwadratowe
hipotezy	Gilbreatha Goldbacha słaba liczb pierwszych bliźniaczych Pólyi

równania
diofantyczne

liniowe	tożsamość Bézouta
kwadratowe	równanie Pitagorasa (trójek pitagorejskich) równanie Pella
wyższych stopni	równanie Fermata (wielkie twierdzenie Fermata) równanie Catalana (twierdzenie Mihăilescu)
układy równań	cegiełka Eulera prostopadłościan idealny
powiązane zagadnienia	dziesiąty problem Hilberta