ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116953
Темы:    [ Разложение на множители ]
[ НОД и НОК. Взаимная простота ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Найдите все такие натуральные k, что при каждом нечётном  n > 100  число  20n + 13n  делится на k.


Решение

  При любом нечётном n число  20n + 13n  делится на  20 + 13 = 33.  Значит, если k является делителем числа 33, то условие выполнено. Докажем обратное.

  Первый способ. Числа  A = 20101 + 13101  и  B = 20103 + 13103  делятся на k. Значит, числа  20²AB = (400 – 169)·13101 = 231·13101  и
B – 13²A = 231·20101  также делятся на k.  (231·20101, 231·13101) = 231 = 7·33,  так что 231 делится на k.
  С другой стороны,  20n + 13n = (20n – 13n) + 2·13n.  Первое слагаемое делится на  20 – 13 = 7,  а второе – нет. Итак, k является делителем числа 231 и не делится на 7; значит, k – делитель числа 33.

  Второй способ. Заметим, что  1 = НОД(20101, 13101) = НОД(20101 + 13101, 20101)  делится на  НОД(20, k).  Следовательно,  НОД(20, k) = 1 . Аналогично
НОД(13. k) = 1.
  Согласно замечанию к задаче 73597 числа  20u – 1  и  13v – 1  кратны k при некоторых натуральных u и v. Рассмотрим такое нечётное число  n > 100,  что  n – 1  кратно uv (например,  n = 1 + 100uv).  Тогда число  (20n + 13n) – 33 = 20(20n–1 – 1) + 13(13n–1 – 1)  делится на k. Следовательно, 33 кратно k.


Ответ

k = 1, 3, 11, 33.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2012-2013
этап
1
Вариант 4
класс
Класс 11
Задача
Номер 11.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .