Никакие два остатка в (7.2.7) не сравнимы по (mod m), так как разность между любыми двумя из них меньше, чем m. Поэтому два числа, которые не сравнимы по (mod m), должны иметь разные остатки. Итак, мы делаем вывод:

сравнение а ≡ b(mod m) выполняется тогда и только тогда, когда числа а и b имеют одинаковые остатки при делении на число m.

Существует другой способ представления этого сравнения. Предположим на мгновение, что а и b — целые положительные числа. Мы видели при обсуждении системы чисел в § 2 главы 6, что когда число а записано при основании m,

а = (а_n…, а₁, а₀) _m,

то последняя цифра а₀ является остатком числа а при делении его на число m. Если мы используем этот факт, чтобы иначе выразить нашу интерпретацию сравнения, то можно сказать:

сравнение а ≡ b (mod m) выполняется для целых (положительных) чисел а и b тогда и только тогда, когда числа а и b имеют одинаковые последние цифры в записи при основании m.

Например,

37 ≡ 87 (mod 10),

так как эти два числа имеют одну и ту же последнюю цифру в десятичной системе чисел.

Система задач 7.2.

1. Найдите остатки —37(mod 7), — 111 (mod 11), — 365 (mod 30).

Из алгебры мы помним, что уравнения можно складывать, вычитать, умножать. Точно такие же правила справедливы для сравнений. Предположим, что мы имеем сравнения

a ≡ b (mod m), с ≡ d (mod m). (7.3.1)

По определению, это означает, что

a = b + mk, c = d + ml, (7.3.2)

где k и l — целые числа. Сложим уравнения (7.3.2).

В результате получаем

а + с = b + d + m (k + l),

что можем записать как

а + с ≡ b + d (mod m); (7.3.3)

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

a — c ≡ b — d (mod m). (7.3.4)

Пример.

11 ≡ —5 (mod 8) и 7 = — 9 (mod 8). (7.3.5)

Складывая их, получаем

18 ≡ — 14 (mod 8),

а вычитая,

4 ≡ 4 (mod 8).

Оба эти сравнения справедливы.

Можно также перемножить два сравнения. Из (7.3.1) и (7.3.2) следует, что

ac = bd + m (kd + bl + mkl),

таким образом,

ас ≡ bd (mod m). (7.3.6)

Пример. Когда два сравнения из (7.3.5) перемножены, получается

77 = 45 (mod 8).

Сравнение a ≡ b (mod m) может быть умножено на любое целое число с, при этом получаем

ас ≡ bc (mod m). (7.3.7)

Это можно рассматривать как частный случай умножения сравнений (7.3.6) при с = d. Его можно также рассматривать как прямое следствие из определения сравнения.

Пример. Когда первое сравнение из (7.3.5) умножается на 3, получаем, что

33 = -15 (mod 8).

Возникает естественный вопрос: в каком случае можно в сравнении (7.3.7) сократить общий множитель с и получить при этом верное сравнение

a ≡ b (mod m)?

Именно здесь сравнения отличаются от уравнений. Например, верно, что

22 ≡ -2 (mod 8),

но сокращение на множитель 2 дало бы сравнение

11 ≡ -1 (mod 8),

которое неверно.

В одном важном случае сокращение допустимо:

если ас ≡ bc (mod m), то a ≡ b (mod m) при условии, что числа m и с взаимно просты.

Доказательство. Первое сравнение означает, что

ас — bc = (а — b) с = mk.

Если D(m, с) = 1, то отсюда следует, что а — b делится на m в соответствии с результатом, доказанным в § 2 главы 4.

Пример. В сравнении

4 ≡ 48 (mod 11)

мы можем сократить на множитель 4, так как D(11, 4) = 1. Это дает

1 ≡ 12 (mod 11).

Система задач 7.3.

1. Придумайте еще несколько примеров на использование изложенных правил действий со сравнениями.