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
edytujWartość 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ż
edytujPrzypisy
edytuj- ↑ 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.).
- ↑ 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.).
- ↑ 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.).