Арифметика по модулю
Начнём с двух главных определений.
Делимость
Целое число 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≡zy или просто x≡y, если понятно, о каком именно модуле (так называется то самое z) идёт речь.
Также мы не будем употреблять слово «модуль» в значении «абсолютная величина».
У сравнимости есть 5 свойств, следующих из её определения:
- для любого x верно, что x≡x по любому модулю
- если x≡ny, то y≡nx
- если x≡ny и y≡nz, то x≡nz
- если x≡ny и a≡nb, то x+a≡ny+b
- если x≡ny и a≡nb, то xa≡nyb
Последнее свойство доказывается не совсем тривиально: нужно ввести обозначения x=y+Xn и a=b+An. После этого свойство становится тривиальным.
Эти свойства позволяют общаться со сравнениями почти так же, как и с обычными равенствами: заменять какие-то подформулы некоей формулы на сравнимые с ними, получая формулу, сравнимую с исходной. Единственное важное отличие: равенство позволяет так делать с любой формулой, а сравнимость — только с формулами, составленными при помощи сложения/вычитания/умножения (но, например, не деления и не возведения в степень).