NT-B2-M02-P001 Таблица квадратов

Достаточно проверить остатки \(0,1,\ldots,15\), но можно отдельно рассмотреть чётные и нечётные числа.

Если число чётно, \(n=2k\), то \(n^2=4k^2\), а \(k^2\pmod4\) равно \(0\) или \(1\), поэтому получаем \(0\) или \(4\). Если число нечётно, прямой вид \(n=2k+1\) даёт \(n^2=4k(k+1)+1\), а \(k(k+1)\) чётно, значит \(n^2\equiv1\) или \(9\pmod{16}\). Итак, возможны \(0,1,4,9\).

Это стартовая таблица для задач на модуль \(16\).