Арифметика по модулю
Арифметика по модулю изучает числа с учётом их остатков при делении на одно и то же число. Она позволяет заменять большие числа меньшими остатками и выполнять вычисления в задачах на теорию чисел.
Запись \(a\equiv b\pmod m\) читают: «\(a\) сравнимо с \(b\) по модулю \(m\)». Условие равносильно тому, что разность \(a-b\) делится на \(m\); свойства делимости помогают быстро проверять такие сравнения. Обычно используют остатки \(0,1,\ldots,m-1\).
Правила операций
Если \(a\equiv b\pmod m\) и \(c\equiv d\pmod m\), то сравнения можно складывать, вычитать и перемножать:
Поэтому при вычислении достаточно заменить каждое число его остатком, а затем снова взять остаток результата. Для степени правило применяется многократно: если \(a\equiv b\pmod m\), то \(a^k\equiv b^k\pmod m\) для любого натурального \(k\).
Найдём остаток числа \(37\cdot24+15\) при делении на \(7\). Так как \(37\equiv2\pmod7\), \(24\equiv3\pmod7\), а \(15\equiv1\pmod7\), получаем \(37\cdot24+15\equiv2\cdot3+1=7\equiv0\pmod7\). Значит, выражение делится на \(7\).
Сравнимость по модулю — не обычное равенство: \(17\equiv2\pmod5\), хотя \(17\ne2\). Кроме того, деление в сравнениях не всегда разрешено. Сокращать множитель можно только с учётом его взаимной простоты с модулем: если \(ac\equiv bc\pmod m\) и \(\gcd(c,m)=1\).
Какой остаток имеет \(2^{10}+3\) при делении на \(5\)?
Главное
- \(a\equiv b\pmod m\) означает, что \(m\) делит \(a-b\), или что числа имеют одинаковые остатки.
- Сравнения сохраняются при сложении, вычитании, умножении и возведении в натуральную степень.
- Большие числа можно заменять остатками, но деление и сокращение требуют дополнительных условий.