Reszty kwadratowe
Jeśli p jest liczbą pierwszą, to resztą kwadratową dla liczby p nazywamy każdą liczbę całkowitą r, dla której istnieje liczba całkowita x taka, że liczba x2 - r jest podzielna przez p.
Liczba całkowita r jest resztą kwadratową dla p, jeżeli istnieje kwadrat liczby całkowitej, dającej przy dzieleniu przez p taką samą resztę jak r. Liczby całkowite, nie będące resztami kwadratowymi dla p, nazywamy nieresztami kwadratowymi dla p.
Resztę kwadratową możemy zdefiniować dla liczb naturalnych za pomocą kongruencji:
Liczbę całkowitą r nazywamy resztą kwadratową modulo n, jeżeli istnieje taka
liczba całkowita x, że x2 ≡ r (mod n).
Natychmiast wnioskujemy, że dla dowolnego n liczba 0 i 1 jest resztą kwadratową modulo n. Dla dowolnego n zachodzi: 02 ≡ 0 (mod n) oraz 12 ≡ 1 (mod n).
Dla liczby pierwszej 2 każda liczba całkowita jest resztą kwadratową, gdyż jeżeli r jest liczbą nieparzystą, to 12 ≡ r (mod 2), jeżeli natomiast r jest liczbą parzystą, to 02 ≡ r (mod 2).
Jeżeli p jest liczbą pierwszą nieparzystą, to w ciągu 1, 2, 3, ..., p-1 mamy dokładnie reszt kwadratowych modulo p.
Z powyższego twierdzenia wynika, że dla otrzymania wszystkich liczb ciągu 1, 2, ..., p-1, będącymi resztami kwadratowymi dla liczby pierwszej nieparzystej p, wystarczy wyznaczyć reszty z dzielenia przez p liczb .
Przykłady w ciągu 1, 2, ..., n-1:
Reszty kwadratowe modulo 7: 1, 4, 2
Reszty kwadratowe modulo 13: 1, 4, 9, 3, 12, 10
Reszty kwadratowe modulo 19: 1, 4, 9, 16, 6, 17, 11, 7
Reszty kwadratowe modulo 8: 1, 4,
Reszty kwadratowe modulo 15: 1, 4, 6, 9, 10