Из алгебры мы помним, что уравнения можно
складывать, вычитать, умножать. Точно такие же правила справедливы для
сравнений. Предположим, что мы имеем сравнения
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. Придумайте еще несколько примеров на использование изложенных правил действий со сравнениями.
| 