Задача 116953

Темы:    [ Разложение на множители ] [ НОД и НОК. Взаимная простота ]

Сложность: 4- Классы: 8,9,10

Условие

Автор: Голованов А.С.

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

Решение

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

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

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

Ответ

k = 1, 3, 11, 33.

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

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