Задачка про остаток

Ответ: 0 или 1 или 4.

Обозначим исходное число n.

Если n нечётно, т. е. n=2k+1 (где k — целое число) , то
n^2 = (2k+1)^2 = 4k^2+4k+1 = 8*(k*(k+1)/2)+1.
Одно из чисел k или k+1 — чётно. Поэтому число k*(k+1)/2 — целое. Следовательно, число n^2 = 8*(k*(k+1)/2)+1, при делении на 8, даёт остаток 1.

Если n чётно, но не делится на 4, то n^2 длится на 4, но не делится на более высокие степени 2 (в частности на 8). Тогда и остаток от деления n^2 на 8 делится на 4, но не делится на 8. Следовательно, этот остаток равен 4.

Если n делится на 4, то n^2 длится на 16, а значит и на 8. Следовательно, в этом случае остаток от деления n^2 на 4 равен 0.