Базовый аппарат сравнений по модулю

Как можно вычислить остаток точного квадрата, если мы знаем, например, остаток самого числа? Пусть остаток нашего числа при делении на 5 равен , то есть число имеет вид , где . Тогда квадрат имеет вид , то есть его остаток при делении на 5 равен остатку при делении на 5 (мы берем именно остаток от него, так как само может быть и не являться уже остатком). Осталось рассмотреть, какие остатки дают квадраты чисел 0, 1, 2, 3 и 4. Это, соответственно, 0, 1, 4, 4, 1.