Задача 109605

Темы:    [ НОД и НОК. Взаимная простота ] [ Делимость чисел. Общие свойства ] [ Последовательности (прочее) ] [ Доказательство от противного ]

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

Условие

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

Последовательность натуральных чисел a_i такова, что  НОД(a_i, a_j) = НОД(i, j)  для всех  i ≠ j.  Докажите, что  a_i = i  для всех  i ∈ N.

Решение

  Так как каждое a_i делится на  НОД(a_i, a_2i) = НОД(i, 2i) = i,  то  a_i ≥ i  для всех  i ∈ N.
  Предположим, что  a_i > i  при некотором i. Тогда, с одной стороны,  НОД(a_i, a_ai) = НОД(i, a_i) = i,  а с другой стороны, поскольку a_ai делится на a_i, то
НОД(a_i, a_ai) = a_i > i.  Противоречие.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1995
Этап
Вариант	5
Класс
Класс	10
задача
Номер	95.5.10.5