§ 3. Алгебра сравнений

§ 3. Алгебра сравнений

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

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