Reszta kwadratowa modulo (gdzie jest liczbą pierwszą) – w teorii liczb, taka liczba całkowita że istnieje rozwiązanie kongruencji:
Jeśli powyższa kongruencja nie ma rozwiązania dla pewnej liczby całkowitej , to taką liczbę nazywamy nieresztą kwadratową modulo .
Własności
Symbol Legendre'a Wartość symbolu Legendre'a określamy wzorem:
Jeśli to . Symbol Legendre’a jest również funkcją ściśle multiplikatywną licznika:
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
Z wykorzystaniem symbolu Legendre'a kryterium to można zapisać następująco: .
Prawo wzajemności reszt kwadratowych Dla różnych liczb pierwszych i większych od 2 zachodzi równość
Przykłady
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
Linki zewnętrzne
Kategoria:Teoria liczb Kategoria:Arytmetyka modularna