Reszta kwadratowa modulo

Reszta kwadratowa modulo p {\displaystyle p} (gdzie p {\displaystyle p} jest liczbą pierwszą) – w teorii liczb, taka liczba całkowita a , {\displaystyle a,} że istnieje rozwiązanie kongruencji[1]:

x 2 ≡ a ( mod p ) . {\displaystyle x^{2}\equiv a{\pmod {p}}.}

Jeśli powyższa kongruencja nie ma rozwiązania dla pewnej liczby całkowitej a {\displaystyle a} , to taką liczbę nazywamy nieresztą kwadratową modulo p {\displaystyle p} [1].

Własności

Symbol Legendre'a

Wartość ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} symbolu Legendre'a określamy wzorem[1][2][3]:

( a p ) = { − 0 , jeśli  p ∣ a , − 1 , jeśli  a  jest resztą kwadratową modulo  p , − 1 , jeśli  a  jest nieresztą kwadratową modulo  p . {\displaystyle \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 ≡ b ( mod p ) , {\displaystyle a\equiv b{\pmod {p}},} to ( a p ) = ( b p ) {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)} [2]. Symbol Legendre’a jest również funkcją ściśle multiplikatywną licznika[1]:

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

Kryterium Eulera

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

a p − 1 2 ≡ 1 ( mod p ) . {\displaystyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}.}

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

( a p ) ≡ a p − 1 2 ( mod p ) {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}} .

Prawo wzajemności reszt kwadratowych

Dla różnych liczb pierwszych p {\displaystyle p} i q {\displaystyle q} większych od 2 zachodzi równość[1]

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

Przykłady

Ta sekcja od 2017-07 zawiera treści, przy których brakuje odnośników do źródeł.
Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.
  • 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. ↑ a b c d e f 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.).
  2. ↑ a b c 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.).
  3. ↑ a b 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.).