Reszta kwadratowa modulo

Reszta kwadratowa modulo $p$ (gdzie $p$ jest liczbą pierwszą) – w teorii liczb, taka liczba całkowita $a,$ że istnieje rozwiązanie kongruencji:

x^{2}\equiv a{\pmod {p}}.

Jeśli powyższa kongruencja nie ma rozwiązania dla pewnej liczby całkowitej $a$ , to taką liczbę nazywamy nieresztą kwadratową modulo $p$ .

Własności

Symbol Legendre'a

Wartość $\left({\frac {a}{p}}\right)$ symbolu Legendre'a określamy wzorem:

\left({\frac {a}{p}}\right)={\begin{cases}{\phantom {-}}0,&{\text{jeśli }}p\mid a,\\{\phantom {-}}1,&{\text{jeśli }}a{\text{ jest resztą kwadratową modulo }}p,\\-1,&{\text{jeśli }}a{\text{ jest nieresztą kwadratową modulo }}p.\\\end{cases}}

Jeśli $a\equiv b{\pmod {p}},$ to $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$ . Symbol Legendre’a jest również funkcją ściśle multiplikatywną licznika:

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

Jeśli $p$ jest liczbą pierwszą większą od 2 i $a$ jest liczbą całkowitą spełniającą $a\not \equiv 0{\pmod {p}}$ , to $a$ jest resztą kwadratową modulo $p$ wtedy i tylko wtedy, gdy zachodzi kongruencja

a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}.

Z wykorzystaniem symbolu Legendre'a kryterium to można zapisać następująco:

\left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}

.

Prawo wzajemności reszt kwadratowych

Dla różnych liczb pierwszych $p$ i $q$ większych od 2 zachodzi równość

\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)\equiv (-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}.

Przykłady

Kwadrat dowolnej liczby całkowitej kończy się jedną z cyfr: 0, 1, 4, 5, 6, 9. Oznacza to, że liczby te są resztami kwadratowymi modulo 10.
Resztami kwadratowymi modulo 8 są liczby 0, 1 i 4. Nieresztami są liczby 2, 3, 5, 6, 7. Wynika stąd, że kwadrat dowolnej liczby nieparzystej daje z dzielenia przez 8 resztę 1.

Zobacz też

Przypisy

1 2 3 4 5 6 JerzyJ. Rutkowski JerzyJ., Teoria liczb w zadaniach, Wydanie I, Warszawa: Wydawnictwo Naukowe PWN, 2018, s. 71-72, ISBN 978-83-01-19874-9 [dostęp 2024-01-22] (pol.).
1 2 3 WładysławW. Narkiewicz WładysławW., Teoria liczb, Wyd. 3 zm, Warszawa: Wydaw. Naukowe PWN, 2003, s. 61-65, ISBN 978-83-01-14015-1 [dostęp 2024-01-22] (pol.).
1 2 AdamA. Neugebauer AdamA., Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 203-204, ISBN 978-83-7267-710-5 (pol.).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-1] 1 2 3 4 5 6 JerzyJ. Rutkowski JerzyJ., Teoria liczb w zadaniach, Wydanie I, Warszawa: Wydawnictwo Naukowe PWN, 2018, s. 71-72, ISBN 978-83-01-19874-9 [dostęp 2024-01-22] (pol.).

[:1-2] 1 2 3 WładysławW. Narkiewicz WładysławW., Teoria liczb, Wyd. 3 zm, Warszawa: Wydaw. Naukowe PWN, 2003, s. 61-65, ISBN 978-83-01-14015-1 [dostęp 2024-01-22] (pol.).

[:2-3] 1 2 AdamA. Neugebauer AdamA., Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 203-204, ISBN 978-83-7267-710-5 (pol.).