Сравнения и их свойства

 

Мы будем рассматривать целые числа в связи с остатками от деления их на целое положительное m, которое назовем модулем (слово “модуль” происходит от латинского слова modulus, что в переволе означает “мера”, “величина”).

Каждому целому числу отвечает определенный остаток от деления его на m; если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m или сравнимыми по модулю m.

Сравнимость чисел a и b по модулю m записывается так:

a º b (mod m)

Сравнимость чисел a и b по модулю m равносильна:

1. Возможности представить a в виде a = b + mt, где t – целое.

2. Делимости a – b на m.

Способ, которым мы записываем сравнения, напоминает нам уравнения, и в действительности, сравнения и алгебраические уравнения имеют много общих свойств. Простейшими из них являются три следующих свойства[2]:

1. a º a (mod m).

Доказательство. Это является следствием того, что

a – a = m×0.

2. Если a º b (mod m), то b º a (mod m).

Доказательство. Это следует из того, что

b – a = –(a – b) = m(–k).

3. Если a º b (mod m) и b º c (mod m), то a º c (mod m).

Доказательство. Из условия следует, что

a – b = mk, b – c = ml,

поэтому

a – c = (a – b) + (b – c) = m(k + l).

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

1. Если a º b (mod m), c º d (mod m), то a + c º b + d (mod m).

Доказательство. Из условия следует, что

a = b + mk, c = b + ml,

где k и l – целые числа. Сложим эти уравнения. В результате получаем

a + c = b + d + m(k + l),

а это означает, что

a + c º b + d (mod m).

2. Если a º b (mod m), c º d (mod m), то a – c º b – d (mod m).

3. Если a º b (mod m), c º d (mod m), то ac º bd (mod m).

4. Если a º b (mod m) и c – произвольное целое число, то ac º bc (mod m). Это свойство является частным случаем предыдущего при c = d.

Свойства 1 и 3 (сложение и умножение сравнений) обобщаются следующей теоремой.

Теорема. Если в выражении многочлена с целыми коэффициентами заменим , x₁, ..., x_k числами , y₁, ..., y_k сравнимыми с прежними по модулю m, то новое выражение S будет сравнимо с прежним по модулю m.

Доказательство. Действительно, из

,

x₁ º y₁ (mod m), ..., x_k º y_k (mod m)

находим (свойство 3)

,

,

откуда, суммируя, получим

.

Следствие. Если a º b (mod m), a₁ º b₁ (mod m), ..., a_n º b_n (mod m), x º y (mod m), то axⁿ + a₁x^n–1 + ... + a_n º byⁿ + b₁y^n–1 + ... + b_n (mod m).

Доказательство. Это утверждение есть частный случай предыдущей теоремы при k = 1.

Возникает естественный вопрос: в каком случае можно в сравнении ac º bc (mod m) сократить общий множитель c и получить при этом верное сравнение a º b (mod m)?

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

22 º –2 (mod 8),

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

11 º –1 (mod 8),

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

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

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

Рассмотрим еще несколько свойств сравнений.

5. Если a º b (mod m) и k – произвольное целое число, то ak º bk (mod mk).

Доказательство. Действительно, из a º b (mod m) следует

a = b + mt, ak = bk + mkt

и, следовательно, ak º bk (mod mk).

6. Обе части сравнения и модуль можно разделить на их общий делитель.

Доказательство. Действительно, пусть

a º b (mod m), a = a₁d, b = b₁d, m = m₁d.

Имеем

a = b + mt, a₁d = b₁d + m₁dt, a₁ = b₁ + m₁t

и, следовательно, a₁ º b₁ (mod m₁).

7. Если a º b (mod m₁), ..., a º b (mod m_k), то a º b (mod HOK(m₁, ..., m_k)), где HOK(...) – наименьшее общее кратное чисел, указанных в скобках.

8. Если сравнение имеет место по модулю m, то оно имеет мето и по модулю d, равному любому делителю числа m.

9. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.

10. Если a º b (mod m), то D(a, m) = D(b, m).