Арифметика остатков
Остатки от деления, в том числе отрицательных чисел, обратный элемент по модулю, линейные сравнения, большие степени по малой теореме Ферма и системы сравнений.
Как решать
В арифметике остатков числа живут на циферблате: после $m - 1$ снова идёт $0$. Складывать, вычитать и умножать можно сразу остатками — результат тот же. Делить — только на числа, у которых есть обратный, то есть взаимно простые с модулем.
По шагам
- Остаток — число от $0$ до $m - 1$. Для отрицательного найдите ближайшее кратное $m$ снизу: $-36 = 24 \cdot (-2) + 12$.
- Обратный к $a$ по модулю $m$: алгоритм Евклида для $a$ и $m$, затем обратный ход — выразите $1$ через $a$ и $m$. Коэффициент при $a$ и есть обратный.
- Сравнение $ax + b \equiv c \pmod m$: перенесите $b$, умножьте обе части на обратный к $a$.
- Большая степень по простому модулю $p$: по малой теореме Ферма $a^{p-1} \equiv 1$, поэтому показатель можно уменьшить по модулю $p - 1$.
Где ошибаются
- Дают отрицательный остаток: $-36 \bmod 24$ — это $12$, а не $-12$.
- «Делят» сравнение на число, не взаимно простое с модулем: из $6x \equiv 4 \pmod{10}$ нельзя просто разделить на $6$.
- Уменьшают показатель по модулю $p$, а не $p - 1$.
- Не проверяют обратный: $a \cdot a^{-1}$ должно давать остаток $1$.