Reszta kwadratowa modulo

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Reszta kwadratowa)

W teorii liczb, resztą kwadratową modulo (gdzie jest liczbą pierwszą) nazywamy taką liczbę całkowitą ż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 | edytuj kod]

Symbol Legendre'a[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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]

Prawo wzajemności reszt kwadratowych[edytuj | edytuj kod]

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

[1]

Przykłady[edytuj | edytuj kod]

  • 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 | edytuj kod]

Przypisy[edytuj | edytuj kod]

  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.).