П.1 Определение и основные свойства сравнений




Пусть — произвольное натуральное число. Будем называть его модулем.

Определение: Целые числа a и b сравнимы по модулю m, если их разность a-b делятся на m.

Обозначение: a b (mod m).

Пример:

17 5 (mod 17), 19 ≡ -1 (mod 10)

15 ≡ 0 (mod 5), 11≡ 1 (mod 5)

Замечание: Сравнение 17 ≡ 5 (mod 12) иллюстрирует хорошо знакомую ситуацию. По модулю 12 мы обычно называем время, говоря "сейчас 5 часов", вместо "сейчас 17 часов".

Теорема 1:Следующее утверждения для целых чисел a и b равносильны:

1) разность a-b делится на m.

2) , где .

3) a и b имеют одинаковые остатки при делении на m.

Доказательство:1) 2) Пусть a-b делятся на m. Тогда a-b=mt

или .

2) 3) Пусть , и пусть b при делении на m имеет остаток r, т.е. . Тогда , где 0 ≤ r < m.

Следовательно r — остаток от деления a на m. Значит, a и b имеют равные остатки от деления на m.

3) 1) Пусть Тогда делится на m.

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

Перейдем к изучению свойств сравнений. Отношение сравнимости двух целых чисел является примером бинарного отношения на множестве Z. Во многом это отношение похоже на отношение равенства. Свойства 1°—4° иллюстрируют это сходство.

1°. Отношение сравнения является отношением эквивалентности:

  1. a ≡ a (mod m)
  2. a ≡ b (mod m) b ≡ a (mod m)
  3. a ≡ b (mod m), b ≡ c (mod m) a ≡ c (mod m)

Доказательство:

1. Рефлексивно очевидна, т.к. a-a делиться на m.

2. Симметричность не менее ясна: если a-b делиться на m, то

b- a тоже делится на m.

3. Транзитивность следует из равенства и свойств делимости.

2°. Сравнения по одному и тому же модулю можно складывать, вычитать и умножать:

если a ≡ b (mod m), c ≡ d (mod m), то

a + c =b + d (mod m)

a - c =b – d (mod m)

a · c =b · d (mod m)

Доказательство:Пусть , , где и — целые.Тогда

что по теореме 1 равносильно требуемым сравнениям.

Пример:

3°. Обе части сравнения можно увеличить на одно и тоже число, домножать на одинаковый множитель или возвести в одинаковую степень:

 

 

если a ≡ b (mod m), то

a + k ≡ b + k (mod m), k Z,

a · k ≡b · k (mod m), k Z,

(mod m), k N.

Доказательство:Требуемые утверждения легко получить, применяя свойство 2° к сравнениям a ≡ b (mod m) и

k k (mod m).

Пример:9 ≡ 4 (mod 5). Для k = 2 получим верные сравнения:

11 ≡ 6 (mod 5), 18 ≡ 8 (mod 5), 81 ≡ 16 (mod 5).

4°. Члены сравнения можно переносить из одной части в другую с переменой знака:

a + b ≡ с (mod m) ac-b (mod m)

Доказательство:Следует из свойства 3° при k = -b.

Следующие два свойства показывают отличие числовых сравнений от обычных равенств.

5°. В любой части сравнения можно добавить или отбросить слагаемое, кратное модулю:

a ≡ b (mod m) a + m · k ≡ b (mod m)

Доказательство: По определению сравнимости:

m · k ≡ 0 (mod m). Складывая это сравнение с данным сравнением

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

Пример:Свойство 5° используют при подсчете дней недели:

3 ≡ b (mod 7) 24 ≡ b (mod 7).

Если 3 числа были вторник, то 24 числа тоже будет вторник.

6°. Обе части сравнения можно сократить на их общий множитель, если он взаимно прост с m:

если a · k ≡ b · k (mod m) и при этом НОД(k,m) = 1,

то a ≡ b (mod m).

Доказательство:Пусть a · k - b · k делится на m. По условию

k и m взаимно простые a-b делиться на m a ≡ b (mod m).

 

Замечание: Условие взаимной простоты k и m очень важно. Вообще говоря, сокращение может привести к неверному результату. Например, 8 ≡ 6 (mod 2), но 4 3 (mod 2). Впрочем, иногда после сокращения на k результат может оказаться верным, хотя k и m не взаимно просты:

Например, 85 ≡ 10 (mod 15).

После сокращения на 5 получим верное сравнение

17 ≡ 2 (mod 15).

Рассмотренные свойства сравнений обобщаются следующее теоремой.

Теорема 2: Пусть — с целыми коэффициентами. Пусть x ≡ y (mod m).

Тогда p(x) ≡ p(y) (mod m).

Если, кроме того, (mod m), i = 0,1,2…n, то

(mod m).

Доказательство:Непосредственно следует из свойств2° и 3°.

Замечание 1: Аналогичная теорема верна и для многочленов от n переменных с целыми коэффициентами. Например,

если (mod m), i =1,2,3…n, то

(mod m).

Замечание 2: Встречающиеся в сравнении показатели степеней, нельзя заменять сравнимыми по модулю m. Иначе говоря, из того, что n ≡ k (mod m) не следует, что

(mod m). Например, 3 ≡ 8 (mod 5), но (mod 5), так как (mod 5), а (mod 5).

 

В свойствах 7° — 10° некоторые манипуляции проводят не только с обеими частями сравнения, но и с модулем m.

7°. Обе части сравнения и модуль можно домножить или сократить на их общий множитель:

a ≡ b (mod m) a · k ≡ b · k (mod mk)

Доказательство:Пусть a ≡ b (mod m). Тогда a = b + m∙t a∙k = b∙k + m∙k∙t a∙k ≡ b∙k (mod mk).

 

Эти же рассуждения можно провести в обратном порядке.

 

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

.

Доказательство:Еслиa-b делиться на m, а m делиться на d, то по транзитивности a-b делиться d a ≡ b (mod d).

9°. Если два числа сравнимы по нескольким модулям, то они сравнимы по модулю, равному наименьшему общему кратному этих модулей:

,

где .

Доказательство: Если , то разность a-b делиться на и на . Значит, (свойство 1 НОК) a-b делиться на , т.е. a ≡ b (mod m). Такое же рассуждение сохраняет силу и для нескольких модулей.

10°. Если a ≡ b (mod m), то множество общих делителей a и m совпадает с множеством общих делителей b и m. В частности НОД(a,m) = НОД(b,m).

Доказательство:Пустьa ≡ b (mod m). Тогда a – b = m∙t.Если d — общий делитель a и m, то — общий делитель b и m. Обратное аналогично.





©2015-2017 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.

Обратная связь

ТОП 5 активных страниц!