Теория чисел на Питергоре
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Даны два нечетных натуральных числа 
и 
Докажите, что существует такое натуральное 
что хотя бы одно из чисел 
и
делится на 
Подсказка 1
Попробуйте рассмотреть обобщенную задачу. "Дано натурально число n и два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел b²ᵏ - a² и a²ᵏ - b² делится на 2ⁿ".
Подсказка 2
Припомните известное утверждение об остатке от деления c²-1 на 2ᵏ⁺², если остаток от деления c-1 на 2ᵏ⁺¹ равен 2ᵏ, где с — некоторое число.
Подсказка 3
Рассмотрим числа a² - 1, которое делится на 2ᵅ и не делится на 2ᵅ⁺¹, и b² - 1, которое делится на 2ᵝ и не делится на 2ᵝ⁺¹. Подумайте, какие ограничения на α и β накладывают приведенные нами условия. Воспользовавшись вышеприведенной леммой, подумайте, какой остаток при делении на 2ᵝ⁺¹ дает число a²ᵐ - 1 (где m = β-α при условии β>α).
Подсказка 4
Примените индукцию по n. Чтобы доказать базу индукции, подумайте, какое число нам подойдет при n ≤ β+1 и почему.
Подсказка 5
Для доказательства шага индукции рассмотрите два случая: когда a²ᵏ - b² делится на 2ⁿ⁺¹ и, соответственно, когда не делится.
Подсказка 6
Если всё ещё испытываете затруднения, положите r = 2ⁿ⁻ᵝ + 1. В очередной раз воспользуйтесь леммой и ответьте на вопрос, какой остаток дает b²ʳ при делении на 2ⁿ⁺¹.
Подсказка 7
Воспользуйтесь формулой разности степеней. Разложив a²ᵏʳ - b²ʳ, Вы получите произведение двух скобок. Оцените делимость какой-либо из них на 2ⁿ⁺¹.
Подсказка 8
a²ᵏʳ - b² = (a²ᵏʳ - b²ʳ) - (b²ʳ - b²). С остатком от деления левой скобки на 2ⁿ⁺¹ разобрались, а что насчёт правой?
Будем решать обобщенную задачу. Дано натуральное число 
и два нечетных натуральных числа 
и 
Докажите, что существует такое
натуральное 
что хотя бы одно из чисел 
и 
делится на 
Воспользуемся следующим известным утверждением: пусть число 
дает остаток 
при делении на 
где 
Тогда
дает остаток 
при делении на 
Пусть 
делится на 
и не делится на 
а 
делится на 
и не делится на 
Очевидно, что при этом
Тогда 
дает остаток 
при делении на 
а 
дает остаток 
при делении на 
Пусть
положим для краткости 
По лемме число 
даёт остаток 
при делении на
Будем решать задачу индукцией по 
Если 
то нам подойдет 
поскольку 
и 
дают равные остатки при
делении на 
Сделаем переход от 
к 
По индукционному предположению при некотором 
число 
делится на 
Если оно делится и на 
то переход сделан. Иначе оно дает остаток 
при делении на 
Пусть 
Тогда по лемме
дает остаток 
при делении на 
Следовательно, 
дает остаток 
при делении на 
Воспользуемся
формулой разности степеней:
Первая скобка дает остаток 
при делении на 
вторая состоит из 
нечетных слагаемых и, значит, нечётна. Стало быть,
разность 
дает остаток 
при делении на 
Но тогда 
делится на 
поскольку
выражения в скобках дают одинаковые остатки при делении на 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
