🕐Из жизниЧасы со стрелками — готовая модель «сравнений». Если сейчас $10$ часов и пройдёт ещё $27$ часов, стрелка покажет $10+27=37$, но на циферблате это то же самое, что $1$ час: $37$ и $1$ дают одинаковый остаток при делении на $12$. Числа, дающие одинаковый остаток при делении на одно и то же число, называют сравнимыми по модулю этого числа.
Определение
≡Сравнение по модулю mЦелые $a$ и $b$ называют сравнимыми по модулю $m$ ($m\ge2$), если каждое из них при делении на $m$ даёт один и тот же остаток — то есть $a-b$ делится на $m$ без остатка. Обозначение: $a \equiv b \pmod m$.
Например, $100 \equiv 1 \pmod 9$, так как $100-1=99$ делится на $9$; а $1000 \equiv -1 \pmod{11}$, так как $1000-(-1)=1001$ делится на $11$.
Свойства сравнений
Сравнения по модулю ведут себя во многом как равенства:
из $a \equiv b$ и $b \equiv c$ следует $a \equiv c \pmod m$;
из $a \equiv b$ и $c \equiv d$ следует $a{+}c \equiv b{+}d$, $a{-}c \equiv b{-}d$, $ac \equiv bd \pmod m$;
из $a \equiv b \pmod m$ следует $a^n \equiv b^n \pmod m$ для любого натурального $n$;
если $P_n(x)$ — многочлен с целыми коэффициентами и $a \equiv b \pmod m$, то $P_n(a) \equiv P_n(b) \pmod m$.
Пример: остаток от деления $2^{29}$ на $11$
1
Заметим: $2^5=32 \equiv -1 \pmod{11}$ (так как $32-(-1)=33$ делится на $11$).
2
Тогда $2^{25}=(2^5)^5 \equiv (-1)^5 = -1 \pmod{11}$, а $2^4=16 \equiv 5 \pmod{11}$.
На интерактиве справа перетащи точку по «циферблату» из $m$ делений — она покажет остаток числа $a$ при делении на $m$.
Признак делимости на 9
Так как $10 \equiv 1 \pmod 9$, для числа $N=a_n\ldots a_1a_0$ (значение многочлена при $x=10$) верно $N \equiv P_n(1) \pmod 9$, где $P_n(1)$ — сумма цифр $N$. Значит, число и сумма его цифр дают одинаковый остаток при делении на $9$ — отсюда классический признак: если сумма цифр делится на $9$, то и само число делится на $9$.
Запомни
🧠Сравнения по модулю
$a \equiv b \pmod m$ означает, что $a-b$ делится на $m$;
сравнения можно складывать, вычитать и перемножать почленно, как равенства;
из $a \equiv b \pmod m$ следует $a^n \equiv b^n \pmod m$ — удобно для остатков от больших степеней;
$10 \equiv 1 \pmod 9$ — основа признака делимости на $9$ через сумму цифр.