Закон предложения

Лекция 

Сравнения 
 

      Определение

      Целое число a сравнимо с целым числом b по модулю m(m - натуральное число), если a и b при делении на m дают одинаковые остатки.

      Записывают  этот факт так:

a

b(mod m).

     Например, нечетные числа 3 и 7 имеют одинаковые остатки при делении на 2 . Остатки, как легко видеть, равны 1. Поэтому 3 7 (mod 2).

Примечание

      Название  операции – сравнение по модулю не случайно, ибо происходит от латинского modulus, что в переводе на русский язык означает «мера», «величина». Определение сравнения было сформулировано в книге К.Ф.Гаусса «Арифметические исследования», изданной в 1801 г.

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

            Упражнение 1.

Выберите все  числа из следующего списка, сравнимые  с 10 по модулю 7:

     3, 22, 17, 38, 33, 8.

(Проверьте себя - верный ответ – 3,38,17). 

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

Свойство 1

Любые два числа сравнимы по модулю 1.

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

Обоснование этого  факта очевидно, ибо все числа делятся на 1 нацело, и остаток от деления на 1 равен 0. 

Свойство 2

Если a

b(mod m), b  c(mod m), то a c(mod m).

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

Пусть a b(mod m), тогда справедливо равенство a – b = mt₁, где t₁ - целое число. Тогда

a = b +mt₁

Аналогично,

  b = c +mt₂.

      Тогда разность

a – c = b + mt₁ – c = c + mt₂+ mt₁ – c = mt₂ + mt₁ = m(t₁ + t₂)

также делится  нацело на m. Поэтому и справедливо a c(mod m). 

Свойство 3.

Пусть   a

b(mod m),

     c

d(mod m).

Тогда a + c

b + d(mod m).

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

      Поскольку a b(mod m), то a = b +mt₁. Эту запись мы уже использовали при доказательстве свойства 2. Так как b  c(mod m), то  c = d +mt₂.

      Тогда после сложения

a + c = b +mt₁ + c = d +mt₂ = b + d + m(t₂ + t₁ ).

Таким образом, нужное утверждение доказано. 

Свойство 4.

Если    a

b(mod m),

          c

d(mod m), то

     a - c

b - d(mod m).

Доказательство  этого свойства полностью аналогично доказательству свойства 3. 

Свойство 5.

Если  a

b(mod m),

     с

d(mod m), то

a∙c

b∙d(mod m).

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

a b(mod m), значит a = b +mt₁.

c d(mod m), то c = d +mt₂.

Тогда a∙c = ( b +mt₁)∙( d +mt₂)= bd + bmt₂ + dmt₁+ m²t₁t₂ = bd + m(bt₂ + dt₁ + mt₁t₂). Свойство доказано.

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

Свойство 6.

Если   a

b(mod m), k – целое число, то

ak

bk(mod m). 

Свойство 7.

Если   a

b(mod m), k – натуральное число, то

a^k

b^k(mod m). 

Объединяя свойства 3, 5, 6 и 7, получим 

Свойство 8.

Если   a

b(mod m),

     с

d(mod m),

        e

f(mod m), то

a ∙ cⁿ + e

b∙ dⁿ + f(mod m). 

      Прежде, чем продолжить ряд свойств, остановимся  на свойстве 6 подробнее.  

Напоним свойство 6.

Если   a b(mod m), k – целое число, то

      ak bk(mod m). 

Получается, что  умножать сравнения на число можно. А можно ли делить?

      Как Вы считаете, можно ли «сократить»  на 3 следующее сравнение:

3 33(mod 10)?

      Конечно можно, так как 1 11(mod 10) – верное равенство. Данный пример дает положительный ответ. Тогда рассмотрим еще один пример: 4 2 (mod 2). Можно ли здесь также сократить сравнение на 2?

Однако здсь ответ отрицательный. Оказалось, что «сократить» это сравнение нельзя, так как при сокращении оно из верного равенства превращается в неверное: 2 не сравнимо по модулю 2  с 1. Значит, не все так просто.

      Поэтому предлагаем следующую формулировку. 

Свойство 9.

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

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

Пусть a b(mod m),d = НОД(a,b).

Тогда a = a₁∙d, b = b₁∙d, где a₁ , b₁- некоторые целые числа. По условию a - b делится на m .

a – b = a₁∙d - b₁∙d = (a₁ - b₁)d = mt.

Итак, произведение (a₁ - b₁)d делится нацело на m. Но, НОД(d, m)=1, поэтому делиться на m может только a₁ - b₁. Это значит, что a₁ b₁(mod m). 

      Можно продолжать формулировать свойства сравнений. Однако, хотелось бы предложить это сделать Вам, учащиеся. Предлагаем самостоятельно сформулировать (в крайнем случае, найти в какой-нибудь книге) еще одно свойство, не приведенное выше. Чтобы интуиция Вас не подвела, и не получилось ложного утверждения, приведите еще и доказательство этого свойства. Вы непременно заметите, какая это увлекательная деятельность – искать что-то новое. А вдруг Ваше свойство не окажется ни в каких книжках. Это будет лично Ваше достижение. Словом, дерзайте.

      А теперь рассмотрим несколько задач. 

Задача 1.

Найти остаток от деления 112¹⁰ на 5.

Решение

Найти ответ  на вопрос задачи, это еще и указать  целое число (от 0 до 4), которое сравнимо с 112 по модулю 5. Как известно, 112 2(mod 5). Тогда по свойству 7 имеем, что

112¹⁰

2¹⁰(mod 5).

      Очевидно, что 2¹⁰ легче посчитать, однако, еще и все, знакомые с компьютером, на память скажут, что это 1024.  Поскольку 1024 4(mod 5), то легко получаем ответ.

Ответ: 4.

Приведем сокращенную  запись решения.

112

2(mod 5)

 по  свойству 7   112¹⁰

2¹⁰(mod 5) 1024(mod 5) 4(mod 5).

Ответ: 4.

Примечание.

     Если  бы степень была существенно больше 10, то можно было дать ответ, не прибегая к явному возведению 2 в степень. Попробуйте найти это решение. 

Задача 2.

Найти остаток от деления 102⁵ + 311⁷ на 10.

Решение

Теперь уже  будем записывать решение в краткой  форме.

102 2(mod 10) по свойству 7  102⁵ 2⁵(mod 10)  32(mod 10)  2(mod 10).

311 1(mod 10) по свойству 7  311⁷ 1⁷(mod 10)  1(mod 10).

По свойству 3  
 
 

                  102⁵ 2(mod 10)

                  311⁷ 1(mod 10)

                  _______________

            102⁵ + 311⁷ 2 + 1(mod 10) 3(mod 10)

Ответ: 3. 

Упражнение 3

В качестве тренировки найдите остаток от деления 12¹⁰∙7⁸ + 5⁷ на 3.

(Ответ –  2) 

Рассмотрим еще  одну задачу из класса олимпиадных  задач по математике. Представленное ниже решение значительно проще. 

Задача 3.

Доказать, что при любом натуральном n число 37ⁿ⁺² + 16ⁿ⁺¹ + 23ⁿ делится нацело на 7.

Решение

37

2(mod 7), так как 37 = 5∙7 + 2.

16

2(mod 7), так как 16 = 2∙7 + 2.

23

2(mod 7), так как 23 = 3∙7 + 2.

Тогда по свойству 7

37ⁿ⁺²

2ⁿ⁺² (mod 7).

16ⁿ⁺¹

2ⁿ⁺¹ (mod 7).

23ⁿ

2ⁿ (mod 7).

                              ____________________

По свойству 3 37ⁿ⁺² + 16ⁿ⁺¹ + 23ⁿ

2ⁿ⁺² + 2ⁿ⁺¹ + 2ⁿ (mod 7). 

Однако,  2ⁿ⁺² + 2ⁿ⁺¹ + 2ⁿ = 2ⁿ(2² + 2 + 1) = 7∙2ⁿ

Это значит,  37ⁿ⁺² + 16ⁿ⁺¹ + 23ⁿ 7∙ 2ⁿ (mod 7). Но число 7∙2ⁿ делится на 7 нацело, значит, его остаток при делении на 7 равен 0. Следовательно, 7∙2ⁿ(mod 7) 0 37ⁿ⁺² + 16ⁿ⁺¹ + 23ⁿ. Это значит, что 37ⁿ⁺² + 16ⁿ⁺¹ + 23ⁿ делится на 7 нацело. Нужное утверждение доказано.