Теорема 1. Целые числа a и b имеют одинаковые остатки при делении на m тогда и только тогда, когда их разность a - b делится на m.
Почему. Если a = mc₁ + r и b = mc₂ + r, то a - b = m(c₁ - c₂). Обратно, если a - b = mc и b = mq + r, то a = m(c + q) + r — остаток тот же.
Определение. Если целые числа a и b дают одинаковые остатки при делении на натуральное число m, говорят, что a и b сравнимы по модулю m, и пишут:
a ≡ b pmod m.
Например, 57 ≡ 2 pmod11, потому что 57 - 2 = 55 делится на 11; -61 ≡ 11 pmod 8: -61 - 11 = -72 делится на 8. Запись a ≡ 0 pmod m означает, что a делится на m, а a ≡ r pmod b — что a даёт при делении на b остаток r (если 0 ≤ r < b).
Часы показывают время «по модулю 12», дни недели повторяются «по модулю 7».
Свойства сравнений (как у равенств):
| Свойство | Запись |
|---|---|
| Рефлексивность | a ≡ a pmod m |
| Симметричность | если a ≡ b pmod m, то b ≡ a pmod m |
| Транзитивность | если a ≡ b и b ≡ c pmod m, то a ≡ c pmod m |
Пример. Число сравнимо с 585 242 по модулю 73. Докажем, что оно сравнимо и с 73 000 001. Оба числа дают при делении на 73 остаток 1, значит, они сравнимы, а по транзитивности наше число сравнимо и со вторым.