Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Пункт 16. Определения и простейшие свойства.




Определение. Пусть а, b Î Z, m Î N. Говорят, что число а сравнимо с b по модулю m, если а и b при делении на m дают одинаковые остатки. Запись этого факта выглядит так:
a º b(mod m).

Согласитесь, что вместо a º b(mod m) гораздо удобнее было бы писать что-нибудь вроде a º m b, но "привычка свыше нам дана, замена счастию она".

Очевидно, что бинарное отношение сравнимости º m (неважно, по какому модулю) есть отношение эквивалентности на множестве целых чисел, а любители алгебры скажут, что это отношение является даже конгруэнцией кольца Z, фактор-кольцо по которой Z/ º m называется кольцом вычетов и обозначается Z m .

Ясно, что число a сравнимо с b по модулю m тогда и только тогда, когда a-b делится на m нацело. Очевидно, это, в свою очередь, бывает тогда и только тогда, когда найдется такое целое число t, что a=b+mt. Знатоки алгебры добавят к этим эквивалентным утверждениям, что сравнимость a с b по модулю m означает, что a и b представляют один и тот же элемент в кольце Z m .

В далекие дни моей бурной молодости понять процесс собирания целых чисел в классы сравнимых между собой по модулю m (классы эквивалентности º m ) мне помогла следующая картинка:

На рисунке 6 изображен процесс наматывания цепочки целых чисел на колечко с m делениями, при этом на одно деление автоматически попадают сравнимые между собой числа. Кстати, эта картинка неплохо объясняет и термин "кольцо".

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

Свойство 1. Сравнения по одинаковому модулю можно почленно складывать.

Доказательство. Пусть a1º b1(mod m), a2º b2(mod m). Это означает, что a 1 =b 1 +mt 1 , a 2 =b 2 +mt 2 . После сложения последних двух равенств получим a 1 +a 2 =b 1 +b 2 +m(t 1 +t 2 ), что означает a 1 +a 2 º b 1 +b 2 (mod m) <MOD&NBSP;M>.

¨

Свойство 2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный.

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

¨

Свойство 3. К любой части сравнения можно прибавить любое число, кратное модулю.

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

¨

Свойство 4. Сравнения по одинаковому модулю можно почленно перемножать и, следовательно,

Свойство 5. Обе части сравнения можно возвести в одну и ту же степень.

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

¨

Как следствие из вышеперечисленных свойств, получаем

Свойство 6. Если
a 0 º b 0 (mod m), a 1 º b 1 (mod m),..., a n º b n (mod m), x º y(mod m),
то a 0 x n +a 1 x n-1 +...+a n º b 0 y n +b 1 y n-1 +...+b n (mod m)

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

Доказательство. Пусть a º b(mod m), a=a 1 d, b=b 1 d. Тогда (a 1 -b 1 ) × d делится на m. Поскольку d и m взаимно просты, то на m делится именно (a 1 -b 1 ), что означает a 1 º b 1 (mod m).

¨

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

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

a º b(mod m) Û a=b+mt Û ak=bk+mkt Û ak º bk(mod mk).

¨

Свойство 9. Если сравнение a º b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Доказательство. Если a º b(mod m 1 ) и a º b(mod m 2 ), то a-b делится на m 1 и на m 2 , значит a-b делится на наименьшее общее кратное m 1 и m 2 .

¨

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

Доказательство очевидно следует из транзитивности отношения делимости: если a º b(mod m), то a-b делится на m, значит a-b делится на d, где d|m.

¨

Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.

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

a º b(mod m) Û a=b+mt....Уф!

¨

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

Пример. Доказать, что при любом натуральном n число 37 n+2 +16 n+1 +23 n делится на 7.

Решение. Очевидно, что 37 º 2(mod 7), 16 º 2(mod 7), 23 º 2(mod 7)

Возведем первое сравнение в степень n+2, второе – в степень n+1, третье – в степень n и сложим:

т.е. 37 n+2 +16 n+1 +23 n делится на 7. Как видите, ровным счетом ничего сложного в решении подобных школьных задач "повышенной трудности" нет.

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

Задачки 1.Докажите, что 3 105 +4 105 делится на 181. 2.Докажите, что число 5 2n-1 × 2 n+1 +3 n+1 × 2 2n-1 при любом натуральном n делится на 19. 3.Найдите остаток от деления числа (9674 6 +28) 15 на 39. 4.При делении натурального числа N на 3 и на 37 получаются, соответственно, остатки 1 и 33. Найдите остаток от деления N на 111. 5.Докажите, что при любых нечетных положительных значениях n число S m =1 n +2 n +3 n +...+m n делится нацело на число 1+2+3+...+m. 6.Докажите, что число 20 15 -1 делится на 11 × 31 × 61. 7.Докажите, что число p 2 -q 2 , где p и q – простые числа, большие 3, делится на 24. 8.Докажите, что если натуральное число делится на 99, то сумма его цифр в десятичной записи не менее 18. 9.Докажите, что если при делении многочлена M(x) с целыми коэффициентами на х-а в частном получится Q(x), а в остатке R, то (1-a)S(Q)=S(M)-R, где через S(A) обозначена сумма коэффициентов многочлена А. 10.Докажите, что ни при каких натуральных n и k, k>1, число 3 n k не делится на 5.
Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...