докажите что степень двойки не может оканчиваться четырьмя одинаковыми цифрами
Лекция 10 теория чисел-2
Лекция 10: Теория чисел-2.
Примеры (применение сравнений и их свойств):
(!) Здесь было проделано совершенно типовое рассуждение для теоретико-числовых задач: взять какой-то модуль, рассмотреть по этому модулю возникающие в задаче выражения, выяснить, что они принимают не все возможные значения и воспользоваться этим. Для таких распространенных выражений, как квадраты и кубы, следует держать на бумажке (а лучше в голове) готовую таблицу остатков по всем модулям до 10-13.
Признаки делимости. В этом параграфе мы откроем завесу тайны над тем, как же доказываются признаки делимости, известные каждому с детства. А также покажем их связь с десятичной записью числа и обычные применения этих признаков в олимпиадных задачах.
Примеры (признаки делимости и соответствующие сравнения):
Задача 2. Может ли сумма цифр точного квадрата равняться 2003?
Решение: Нет, не может: 2003=2 (mod 3), а точные квадраты несравнимы с 2 по mod 3 (вычислялось выше).
Теоремы Ферма и Эйлера. Наконец, мы познакомимся с фундаментальным фактом, который поможет многократно сократить вычисления значений степеней по модулям.
Утверждение 1. Пусть ka=kb (mod n), k и n взаимно просты. Тогда a=b (mod n).
Доказательство : Если ka=kb (mod n), то n|ka-kb, т.е. n|k(a-b). Так как (k,n)=1, то n|a-b, что и значит a=b (mod n).
Задача 3. Целое число a не делится на простое p. Докажите, что существует такое целое b, что ab=1 (mod p).
Решение: В соответствии с малой теоремой Ферма, подойдет b=a p-2 или любое сравнимое с ним по mod p.
По-научному, такое b называется «обратным к a к приведенном кольце вычетов».