Reszta kwadratowa modulo

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

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

Własności

edytuj

Wartość   symbolu Legendre'a określamy wzorem[1][2][3]:

 

Jeśli   to  [2]. Symbol Legendre’a jest również funkcją ściśle multiplikatywną licznika[1]:

 

Jeśli   jest liczbą pierwszą większą od 2 i   jest liczbą całkowitą spełniającą  , to   jest resztą kwadratową modulo   wtedy i tylko wtedy, gdy zachodzi kongruencja[1]

 

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

 .

Dla różnych liczb pierwszych   i   większych od 2 zachodzi równość[1]

 

Przykłady

edytuj
  • 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ż

edytuj

Przypisy

edytuj
  1. a b c d e f Jerzy Rutkowski, 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ław Narkiewicz, 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 Adam Neugebauer, Algebra i teoria liczb, wyd. 2, Kraków: Wydawnictwo Szkolne OMEGA, 2020 (Matematyka olimpijska), s. 203-204, ISBN 978-83-7267-710-5 (pol.).