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
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]:
Kryterium Eulera
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
![]() | 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ż
- kryterium Eulera
- niereszta kwadratowa modulo
- symbol Jacobiego
- symbol Legendre’a
Przypisy
- ↑ 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.).
- ↑ 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.).
- ↑ 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.).