Арифметика по модулю
Начнём с двух главных определений.
Делимость
Целое число \(x\) делится на целое число \(y\) тогда и только тогда, когда существует целое \(z\), для которого \(x=yz\).
В частности:
- 2 делится на 1
- 5 делится на 5
- 5 не делится на 3
- 1 не делится на 2
- 0 делится на любое целое число
- в том числе, 0 делится на 0
- 1 делится только на 1 и на -1
В литературе часто используется обозначение \(x\,|\,y\) для высказывания «\(y\) делится на \(x\)». Это обозначение читают как «\(x\) делит \(y\)».
Сравнимость
Целые числа \(x\) и \(y\) сравнимы по модулю \(z\) тогда и только тогда, когда \((x-y)\) делится на \(z\).
Мы будем использовать обозначение \(x\equiv_z y\) или просто \(x\equiv y\), если понятно, о каком именно модуле (так называется то самое \(z\)) идёт речь.
Также мы не будем употреблять слово «модуль» в значении «абсолютная величина».
У сравнимости есть 5 свойств, следующих из её определения:
- для любого \(x\) верно, что \(x\equiv x\) по любому модулю
- если \(x\equiv_n y\), то \(y\equiv_n x\)
- если \(x\equiv_n y\) и \(y\equiv_n z\), то \(x \equiv_n z\)
- если \(x\equiv_n y\) и \(a\equiv_n b\), то \(x+a\equiv_n y+b\)
- если \(x\equiv_n y\) и \(a\equiv_n b\), то \(xa\equiv_n yb\)
Последнее свойство доказывается не совсем тривиально: нужно ввести обозначения \(x=y+Xn\) и \(a=b+An\). После этого свойство становится тривиальным.
Эти свойства позволяют общаться со сравнениями почти так же, как и с обычными равенствами: заменять какие-то подформулы некоей формулы на сравнимые с ними, получая формулу, сравнимую с исходной. Единственное важное отличие: равенство позволяет так делать с любой формулой, а сравнимость — только с формулами, составленными при помощи сложения/вычитания/умножения (но, например, не деления и не возведения в степень).