Loading [MathJax]/jax/output/HTML-CSS/jax.js

Арифметика по модулю

Начнём с двух главных определений.

Делимость

Целое число 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 тогда и только тогда, когда (xy) делится на z.

Мы будем использовать обозначение xzy или просто xy, если понятно, о каком именно модуле (так называется то самое z) идёт речь.

Также мы не будем употреблять слово «модуль» в значении «абсолютная величина».

У сравнимости есть 5 свойств, следующих из её определения:

  1. для любого x верно, что xx по любому модулю
  2. если xny, то ynx
  3. если xny и ynz, то xnz
  4. если xny и anb, то x+any+b
  5. если xny и anb, то xanyb

Последнее свойство доказывается не совсем тривиально: нужно ввести обозначения x=y+Xn и a=b+An. После этого свойство становится тривиальным.

Эти свойства позволяют общаться со сравнениями почти так же, как и с обычными равенствами: заменять какие-то подформулы некоей формулы на сравнимые с ними, получая формулу, сравнимую с исходной. Единственное важное отличие: равенство позволяет так делать с любой формулой, а сравнимость — только с формулами, составленными при помощи сложения/вычитания/умножения (но, например, не деления и не возведения в степень).