Если коротко, “остаток” $r$ при делении числа $a$ на $m$ — это единственное число из $\{0,1,\dots,m-1\}$, для которого верно

для некоторого целого $q$ (частного). В повседневных задачах это то, что “остаётся”, когда делим нацело.

Ниже — как я решаю задачи на остатки (модульную арифметику) на практике.

1) Базовое деление с остатком

• Нахожу $q=\left\lfloor \dfrac{a}{m}\right\rfloor$, потом $r=a-qm$.

• Пример: $29 \div 6$. $\lfloor 29/6\rfloor=4$, $r=29-4\cdot6=5$. Ответ: остаток $5$.

Отрицательные числа

Остаток всегда берут неотрицательным.

• Пример: $-29 \bmod 6$. Можно: сначала $-29 \equiv -29+30=1 \pmod 6$. Остаток $1$.

• Универсальная формула: $\big((a \bmod m)+m\big)\bmod m$.

2) Свойства “по модулю”

Они позволяют считать большие выражения по частям, заменяя числа их остатками:

• $(a\pm b)\bmod m \equiv (a\bmod m \pm b \bmod m)\bmod m$

• $(ab)\bmod m \equiv \big((a\bmod m)(b\bmod m)\big)\bmod m$

• $a\equiv b\pmod m \Rightarrow a$ и $b$ дают одинаковые остатки при делении на $m$.

Пример (сумма): найти $(123456+789012)\bmod 9$.
$123456\bmod 9$: сумма цифр $1+2+3+4+5+6=21\Rightarrow 21\bmod 9=3$.
$789012\bmod 9$: $7+8+9+0+1+2=27\Rightarrow 0$.
Итого $3+0\equiv 3\pmod 9$. Остаток $3$.

Пример (произведение): $(314159\cdot 271828)\bmod 7$.
$314159\bmod 7 \equiv 314159-7\cdot44879=314159-314153=6$.
$271828\bmod 7 \equiv 271828-7\cdot38832=271828-271824=4$.
Ответ: $6\cdot4=24\equiv 3\pmod 7$. Остаток $3$.

3) Быстрые признаки для “популярных” модулей

• $\bmod 2$: последняя цифра (чётность).

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

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

• $\bmod 5$: последняя цифра $0$ или $5$.

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

• $\bmod 3$ и $\bmod 9$: сумма цифр.

• $\bmod 11$: разность суммы цифр на чётных и нечётных местах.

Пример: $456789\bmod 8$. Смотрим “789”: $8\cdot98=784$, остаток $5$.

4) Степени: циклы, малые теоремы и быстрое возведение

Часто нужно, например, $a^{n}\bmod m$. Тут выручает:

• Цикл остатков: последовательность остатков степеней периодична.

  • Пример: $2^k\bmod 7$