Утверждение (для модуля 4): при делении $n^2$ на 4 остаток может принимать ровно два различных значения: $0$ или $1$.
Доказательство (связь с чётностью). Если $n$ чётно, $n=2k$, то
$$n^2=(2k{)}^2=4k^2\equiv 0(\mathrm{mod}4).$$ Если $n$ нечётно, $n=2k+1$, то
$$n^2=(2k+1{)}^2=4k(k+1)+1\equiv 1(\mathrm{mod}4),$$ потому что $k(k+1)$ — целое. Значит возможные остатки при делении $n^2$ на 4 — только $\{0,1\}$; чётность $n$ полностью определяет остаток: чётное $\mapsto 0$, нечётное $\mapsto 1$.
Расширение на модуль 8: остатки квадратов по модулю 8 равны только $0,1,4$. Доказательство: пусть $n=2k$ (чётное), тогда
$$n^2=4k^2.$$ Если $k$ чётно, $k=2m$, то $n^2=16m^2\equiv 0(\mathrm{mod}8)$; если $k$ нечётно, то $k=2m+1$ и $n^2=4(2m+1{)}^2\equiv 4(\mathrm{mod}8)$. Для нечётного $n=2k+1$ имеем
$$n^2=4k(k+1)+1,$$ а $k(k+1)$ чётно, следовательно $4k(k+1)$ кратно 8, и $n^2\equiv 1(\mathrm{mod}8)$. Итого возможные остатки: $\{0,1,4\}$. Замечание: для модуля 8 чётности $n$ уже недостаточно — нужно знать чётность $k=n/2$.
Расширение на модуль 3: остатки квадратов по модулю 3 равны только $0$ и $1$. Доказательство: возможные остатки $n$ по модулю 3 — $0,1,2$, и
$$0^2\equiv 0,1^2\equiv 1,2^2\equiv 4\equiv 1(\mathrm{mod}3).$$ Таким образом квадратичные вычеты по модулю 3 образуют множество $\{0,1\}$.
(Общее замечание: для произвольного модуля $m$ множество возможных остатков квадратов — это множество квадратичных вычетов по модулю $m$; его структура зависит от разложения $m$ на простые множители.)