Равенство по модулю

Вы можете встретить следующее выражение:

Это значит, что $A$‍ равно $B$‍ по модулю $C$‍.

Обсудим сравнение по модулю, проделав мысленный эксперимент с оператором деления по модулю.

Представим, что мы делим по модулю 5 все целые числа:

Подпишем 5 секторов цифрами 0, 1, 2, 3 и 4. Затем, каждое целое число мы записываем в сектор, соответствующий результату деления этого числа по модулю 5.
Представьте, что сектор — это корзина, в которую помещаются числа. Например, число 26 положим в корзину с подписью 1, поскольку $26\text{ mod }5=\mathbf{1}$‍.
На рисунке выше приведены примеры чисел, которые окажутся в каждом из секторов.

Было бы полезно придумать способ как обозначить числа, оказавшиеся в одном секторе. (Обратите внимание, что число 26 в примере выше оказалось в одном секторе с числами 1, 6, 11, 16, 21).

Как правило, чтобы показать, что два значения находятся в одном секторе, говорят, что они принадлежат одному классу эквивалентности.
В случае с модулем C математическое обозначение выглядит так: $A\equiv B(\text{mod }C)$‍

Читается это выражение так: $A$‍ равно (или тождественно) $B$‍ по модулю $C$‍.

Изучим его подробнее:

например, $26\equiv 11(\text{mod }5)$‍

$26\text{ mod }5=1$‍, значит, оно находится в одном классе эквивалентности с 1,
$11\text{ mod }5=1$‍, значит, оно также находится в одном классе эквивалентности с 1.

Обратите внимание, что это не то же самое что $A\text{ mod }C$‍: $26\ne 11\text{ mod }5$‍.

Мы можем изучить свойства сравнения по модулю, проведя тот же мысленный эксперимент над натуральным числом $C$‍.
Сначала отметим $C$‍ секторы числами $0,1,2,\dots ,C-2,C-1$‍.
Затем мы поместим каждое целое число в сектор, соответствующий этому целому числу $\text{mod }C$‍.
Ниже на иллюстрации приведены примеры чисел, которые окажутся в каждом секторе.

Если взглянуть на корзину с надписью 0, мы найдём в ней:

Если мы заглянем в корзину с надписью 1, то мы там обнаружим:

Если мы заглянем в корзину с надписью 2, то мы там обнаружим:

Если мы заглянем в корзину с $C-1$‍, то мы там обнаружим:

Из этого эксперимента мы можем сделать следующий вывод.
Числа в каждой из корзин равняются подписи плюс-минус некое кратное числу $\mathbf{C}$‍.
Это значит, что разность между любыми двумя числами в одном секторе — это целое число, кратное $\mathbf{C}$‍.
Это наблюдение поможет нам понять дальнейшие эквивалентные выражения и классы эквивалентности.