Сравнения

Лекция

Сравнения

Определение

Целое число 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 = mt1, где t1 - целое число. Тогда

a = b +mt1

Аналогично,

b = c +mt2.

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

a – c = b + mt1 – c = c + mt2+ mt1 – c = mt2 + mt1 = m(t1 + t2)

также делится нацело на 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 +mt1. Эту запись мы уже использовали при доказательстве свойства 2. Так как b c(mod m), то c = d +mt2.

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

a + c = b +mt1 + c = d +mt2 = b + d + m(t2 + t1 ).

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

Свойство 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 +mt1.

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

Тогда a∙c = ( b +mt1)∙( d +mt2)= bd + bmt2 + dmt1+ m2t1t2 = bd + m(bt2 + dt1 + mt1t2). Свойство доказано.

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

Свойство 6.

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

ak bk(mod m).

Свойство 7.

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

ak bk(mod m).

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

Свойство 8.

Если a b(mod m),

с d(mod m),

e f(mod m), то

a ∙ cn + e b∙ dn + 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 = a1∙d, b = b1∙d, где a1 , b1- некоторые целые числа. По условию a - b делится на m .

a – b = a1∙d - b1∙d = (a1 - b1)d = mt.

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

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

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

Задача 1.

Найти остаток от деления 11210 на 5.

Решение

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

11210 210(mod 5).

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

Ответ: 4.

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

112 2(mod 5)

по свойству 7 11210 210(mod 5) 1024(mod 5) 4(mod 5).

Ответ: 4.

Примечание.

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

Задача 2.

Найти остаток от деления 1025 + 3117 на 10.

Решение

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

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

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

По свойству 3

1025 2(mod 10)

3117 1(mod 10)

_______________

1025 + 3117 2 + 1(mod 10) 3(mod 10)

Ответ: 3.

Упражнение 3

В качестве тренировки найдите остаток от деления 1210∙78 + 57 на 3.

(Ответ – 2)

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

Задача 3.

Доказать, что при любом натуральном n число 37n+2 + 16n+1 + 23n делится нацело на 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

37n+2 2n+2 (mod 7).

16n+1 2n+1 (mod 7).

23n 2n (mod 7).

____________________

По свойству 3 37n+2 + 16n+1 + 23n 2n+2 + 2n+1 + 2n (mod 7).

Однако, 2n+2 + 2n+1 + 2n = 2n(22 + 2 + 1) = 7∙2n

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

Задачи для самостоятельного решения

1. Найти остаток от деления а) 31520 на 15;

б) 1021300 на 3;

в) 5100 + 1310 на 4;

г) 11100 ∙ 222 на 5.

2. Найти остаток от деления 520 ∙ + 134 на 4.

3. Доказать, что на 3105 + 4105 делится нацело на 181.

4. Найти остаток от деления (96746 + 28)15 на 39.

5. При делении натурального числа n на 3 получается остаток 1, а при делении n на 37, остаток равен 33. Найдите остаток от деления n на 111.

6. Доказать, что p2 – q2 делится нацело на 24, если p, q – простые числа, большие 3.

7. Доказать, что если натуральное число делится на 99, то сумма его цифр в десятичной записи не менее 18.

Часть 2.

Решение сравнений первой степени.

Определение

ax b (mod m), где

называют сравнением первой степени.

Решить сравнение, значит, найти x по модулю m.

Пример

Решить сравнение первой степени 5x 9 (mod 11).

Решение

Из 5x 9 (mod 11) следует, что 5x – 9 = 11t или 5x – 11t = 9.

Имеем линейное уравнение с двумя неизвестными, которое мы умеем решать в целых числах.

НОД(5,11) = 1. Поэтому решение этого уравнения ищем в виде

, где x0, t0 - частное решение уравнения, k,m-целые числа.

Найдем частное решение уравнения, причем такое, что x0- лежит между 0 и 10, так как мы решаем сравнение по модулю 11. А ведь остатки от деления на 11 лежат между 0 и 10.

Очевидно, что такое решение всегда существует, если вообще есть решение уравнения.

Поэтому, осуществим некоторый перебор от 0 до 10. Пусть x0= 0. Тогда при подстановке этого значения имеем

0 – 11t0 = 9,

что требует нецелого t0 (равного ). Значит, такое x0 нас не удовлетворит.

Пусть x0= 1. Получим 5∙1 - 11t0 = 9, откуда t0 = . Опять нецелое число.

Проверки для x0= 2 и x0= 3 также приводят нецелому значению t0. Однако, при x0=3 получаем

5∙4 - 11t0 = 9

или

11t0 = 11.

Это уравнение имеет целое решение t0 = 1. Тогда можно выписать решение для x:

x = 11k + 4.

Последняя запись, означает, что остаток от деления x на 11 равен 4, то есть

x 4 (mod 11).

Ответ: x 4 (mod 11).

Задачи для самостоятельного решения.

Решите сравнения

а) 5x 3 (mod 12);

б) 6x 7 (mod 3);

в) 9x 6 (mod 3);

г) 7x 9 (mod 17);

д) 256x 179 (mod 337).