Лекция 5. Тема Теория сравнений 15. Сравнения в кольце целых чисел и их свойства 15 Сравнения по фиксированному модулю
![]()
|
Тема 2. Теория сравнений § 15. Сравнения в кольце целых чисел и их свойства 15.1. Сравнения по фиксированному модулю Опр.1 Целые числа а и b сравнимы между собой по модулю (натуральному числу) m (m > 1) и пишут ![]() Пример. ![]() ![]() ![]() Теорема1. Если целые числа а и b сравнимы по модулю m, то (а – b) ![]() Доказательство: т.к. ![]() а – b = m(q1 – q2) ![]() ![]() Опр.2 Целые числа а и b сравнимы по модулю m (m > 1), если (а – b) ![]() Теорема2. Отношение сравнимости на множестве целых чисел Z является отношением эквивалентности. Доказательство: покажем, что отношение сравнимости по данному модулю m обладает рефлексивностью, т.е. ![]() а – а = 0, а 0 делится на любое число, значит 0 ![]() ![]() Покажем, что отношение сравнимости по данному модулю m обладает симметричностью, т.е. ![]() ![]() ![]() Покажем, что отношение сравнимости по данному модулю m обладает транзитивностью, т.е. ![]() ![]() ![]() ![]() а – с = ((а – b) + (b – c)) ![]() ![]() ![]() ![]() ![]() Свойства 10. Обе части сравнения можно умножать на любое целое число n. Доказательство: покажем, что ![]() ![]() ![]() ![]() ![]() 20. К обеим частям сравнения можно прибавлять любое целое число. Доказательство: покажем, что ![]() ![]() (а + n) – (b + n) = (a + b) ![]() ![]() 30. Сравнения по одному модулю можно складывать и вычитать. Доказательство: покажем, что ![]() ![]() (а ± c) – (b ± d) = (a - b) ![]() ![]() ![]() ![]() 40. Сравнения по одному модулю можно перемножать. Доказательство: покажем, что ![]() ![]() (а c) – (bd) = (aс - bс) ![]() (а- b) ![]() ![]() ![]() 50. Из одной части сравнения слагаемые можно переносить в другую часть с противоположным знаком. Доказательство: покажем, что ![]() ![]() ![]() ![]() ![]() ![]() 60. К любой части сравнения можно прибавить произвольное целое число, кратное модулю, т.е. ![]() ![]() Доказательство: ![]() ![]() ![]() ![]() ![]() 70. Сравнения можно возводить в любую натуральную степень: ![]() ![]() ![]() Доказательство: методом математической индукции. 1. n = 1 ![]() 2. n = k. Пусть верно ![]() 3. Покажем, что формула верна для n = k + 1. Имеем ![]() ![]() ![]() 80. Обе части сравнения можно делить на их общий делитель d, взаимно простой с m. Доказательство: покажем, что ![]() ![]() ![]() ![]() Т.к. а ![]() ![]() ![]() ![]() ![]() a1 = ![]() ![]() ![]() 90. Если в выражении f(a1, a2, …,ak) = ![]() ![]() ![]() Доказательство: по условию ![]() ![]() ![]() ![]() ![]() ![]() По условию ![]() ![]() ![]() ![]() ![]() И f(a1, a2, …,ak) ![]() ![]() Следствие. Если в многочлене с целыми коэффициентами f(x) = anxn + an-1xn-1 + …+a1x + a0, определенном на множестве целых чисел Z, заменить коэффициенты an, an-1, …a1, a0 коэффициентами bn, bn-1, …b1, b0, сравнимыми по модулю m соответственно, то многочлен g(x) = bnxn + bn-1xn-1 + …+b1x + b0сравним с данным многочленом f(x) при любом целом х. Доказательство: пусть ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 15.2. Свойства сравнений 10. Все части сравнения ![]() Доказательство: (а – b) ![]() ![]() ![]() 20. Обе части сравнения ![]() Доказательство: пусть а ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 30. Если ![]() ![]() ![]() Доказательство: т.к. : ![]() ![]() ![]() ![]() ![]() 40. Если ![]() ![]() ![]() ![]() Доказательство: (а – b) ![]() ![]() ![]() ![]() 50. Если одна часть сравнения ![]() Доказательство: пусть а ![]() ![]() ![]() (а – b) ![]() ![]() Т.к. а ![]() ![]() ![]() ![]() ![]() 60. Если ![]() Доказательство: обозначим Da,m – множество общих делителей чисел а и m, Db,m – множество общих делителей чисел b и m. Пусть ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() С другой стороны, пусть ![]() ![]() ![]() ![]() Из (1) и (2) следует, что Db,m ![]() § 16. Вывод признаков делимости Одним из методов нахождения делителя, основанных на сравнении, является метод Паскаля. Пусть некоторое натуральное число а, записанное в системе счисления с основанием q, имеет вид: а = аnqn + an-1qn-1 + …+ a1q + a0, где 0 ![]() ![]() ![]() ![]() Пример. Рассмотрим числа 3, 9. Запись в десятичной системе счисления: а = аn10n + an-110n-1 + …+ a110 + a0. При делении 10к на 3 и на 9 в остатке получается 1, т.е. r0 = r1 = …= rn = 1 и тогда b = аn1 + an-11+ …+ a11 + a0 = аn + an-1+ …+ a1 + a0 . Вывод: натуральное число а делится на 3 (на 9) тогда и только тогда, когда на 3 (на 9) делится сумма цифр этого числа, записанного в десятичной системе счисления. Выведем признак делимости на 11. Заметим, что четная степень 102к при делении на 11 в остатке дает 1, а при делении нечетной степени числа 102к – 1 на 11 в остатке дает -1. Тогда b = a0 + a1(-1) + а2 + а3 (-1)+ а4 + … = (a0 + а2 + а4 + …) – (a1 + а3 + а5 + …). Итак, натуральное число делится на 11 тогда и только тогда, когда разность между суммой цифр, стоящих на четных местах и суммой цифр, стоящих на нечетных местах, делится на 11. Пример. Делится ли на 11 число 53746? Решение: 6 + 7 + 5 – (3 + 4) = 18 – 7 = 11 – делится на 11, значит и 53746 тоже делится на 11. |