Reszty i niereszty kwadratowe
Jeśli $m$ jest liczbą całkowitą, to resztą kwadratową dla liczby $m$ nazywamy każdą liczbę całkowitą $r$, dla której istnieje liczba całkowita $n$ taka, że liczba $n^2-r$ jest podzielna przez $m$. Innymi słowy, liczba całkowita $r$ jest resztą kwadratową dla $m$, jeżeli istnieje kwadrat liczby całkowitej, dającej przy dzieleniu przez $m$ taką samą resztę jak $r$. Liczby całkowite nie będące resztami kwadratowymi dla $m$, nazywamy nieresztami kwadratowymi dla $m$.
Resztę kwadratową możemy zdefiniować za pomocą kongruencji. Liczbę całkowitą $r$ nazywamy resztą kwadratową modulo $m$, jeżeli istnieje taka liczba całkowita $n$, że $n^2 \equiv r \pmod m$. Kongruencja ma rozwiązanie wtedy i tylko wtedy, gdy istnieje taka liczba całkowita $n$, że jej kwadrat przy dzieleniu przez $m$ daje taką samą resztę co liczba $r$.
Aby wyznaczyć dla danego modułu $m$ liczby całkowite $r$, dla których kongruencja jest prawdziwa, wystarczy znaleźć wszystkie reszty kwadratowe modulo $m$. Jeśli liczba $r$ jest resztą kwadratową modulo $m$, to każda liczba przystająca do $r$ modulo $m$ jest także resztą kwadratową dla tego modułu. Należy więc zbadać, które z liczb ciągu $0,1,2,\ldots, m-1$ są resztami kwadratowymi modulo $m$. Dla otrzymania wszystkich takich liczb wystarczy wyznaczyć reszty dzielenia przez $m$ liczb $0^2, 1^2, 2^2, \ldots, k^2$, gdzie $k$ jest częścią całkowitą z liczby $\frac {m}{2}$.
Wyznaczmy wszystkie reszty kwadratowe modulo $10$.
Resztami z dzielenia przez $10$ liczb $0^2, 1^2, 2^2, 3^2, 4^2, 5^2$ są odpowiednio $0,1,4,9,6,5$.
Liczba $10$ ma więc $6$ reszt kwadratowych. Wynika stąd, że ostatnią cyfrą liczby kwadratowej może być jedna z cyfr $0,1,4,9,6,5$.
Dla modułu $12$, resztami przy dzieleniu przez $12$ liczb $0^2, 1^2, 2^2, 3^2, 4^2, 5^2, 6^2$ są odpowiednio liczby $0,1,4,9,4,1,0$.
Liczba $12$ ma wiec cztery reszty kwadratowe $0,1,4,9$. Wszystkie pozostałe reszty z przedziału $$ są nieresztami kwadratowymi
modulo $12$, czyli $3,5,6,7,8,10,11$.
Przykłady
$m = 7$; reszty kwadratowe: $0, 1, 2, 4$
$m = 13$; reszty kwadratowe: $0, 1, 3, 4, 9, 10, 12$
$m = 8$; reszty kwadratowe: $0, 1, 4$
Dla dowolnego modułu $m$ liczba $0$ i $1$ jest resztą kwadratową modulo $m$, bowiem dla dowolnego $m$ zachodzą kongruencje $0^2 \equiv 0 \pmod m$ oraz $1^2 \equiv 1 \pmod m$. Przy obliczaniu liczby reszt kwadratowych często pomija się resztę $0$ uwzględniając tylko liczby naturalne mniejsze od $m$ będące resztami kwadratowymi modulo $m$.
Jeżeli liczba $m$ jest liczbą pierwszą nieparzystą $p$, to reszty dzielenia przez $p$ liczb $1^2, 2^2, \ldots, k^2$, gdzie $k = \frac {p-1}{2}$, są parami różne. Oznacza to, że dla liczb pierwszych otrzymujemy dokładnie $\frac {p-1}{2}$ reszt kwadratowych nie wliczając reszty $0$.