Коротко: остаток от деления целого $a$ на целое $m\neq 0$ — это число $r$ из диапазона $0\le r<|m|$, такое что
$a=mq+r$ для некоторого целого $q$. Обозначают $r=a\bmod m$.

Как находить на практике

1) Обычное «столбиком»

Подходит всегда. Делите $a$ на $m$, берёте целую часть частного $q$, затем $r=a-mq$.
Пример: $257\div 12$. Целая часть $q=21$, $r=257-12\cdot 21=257-252=5$.

2) Через пол: $r=a-m\lfloor a/m\rfloor$

Удобно, если есть калькулятор деления с целой частью.
Пример: $a=257, m=12\Rightarrow \lfloor 257/12\rfloor=21\Rightarrow r=257-12\cdot21=5$.

3) Приведение по модулю (разбиваем число на удобные куски)

Используем, когда число большое: сокращаем его по частям, заменяя куски на их остатки.

Базовые правила:

• $(x+y)\bmod m=((x\bmod m)+(y\bmod m))\bmod m$

• $(x-y)\bmod m=((x\bmod m)-(y\bmod m))\bmod m$ (если получилось отрицательно — добавьте $m$)

• $(xy)\bmod m=((x\bmod m)(y\bmod m))\bmod m$

• Степени: $x^k\bmod m$ считаем повторным возведением и сокращением (быстрое возведение в степень по модулю)

Пример (сумма/умножение): найдите $2025\cdot 1234 \bmod 7$.
$2025\bmod 7=(2000+25)\bmod 7=(2000\bmod 7+25\bmod 7)=(6+4)\bmod 7=3$.
$1234\bmod 7=(1200+34)\bmod 7=(1200\bmod 7+34\bmod 7)=(…0+6)=6$.
Итог: $3\cdot 6\bmod 7=18\bmod 7=4$.

Пример (степень): $3^{100}\bmod 8$.
$3^2=9\equiv1\pmod 8\Rightarrow 3^{100}=(3^2)^{50}\equiv 1^{50}\equiv 1$.

4) Использование «хвоста» числа

Для некоторых модулей достаточно последних цифр:

• $\bmod 2$: последняя цифра чётная? Остаток $0$ или $1$.

• $\bmod 4$: достаточно последних двух цифр.

• $\bmod 8$: достаточно последних трёх цифр.

• $\bmod 5$: последняя цифра $0,5\Rightarrow$ остаток $0$ или $…$

• $\bmod 25$: последние две цифры.

• $\bmod 125$: последние три цифры.
  Пример: $123456\bmod 8$. Берём «456»: $456=8\cdot57+0\Rightarrow r=0$