Задача 66023

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

Сложность: 3+ Классы: 9,10,11

Условие

Авторы: Богданов И.И., Кожевников П.А.

Изначально на доске записаны несколько натуральных чисел (больше одного). Затем каждую минуту на доску дописывается число, равное сумме квадратов всех уже записанных на ней чисел (так, если бы на доске изначально были записаны числа 1, 2, 2, то на первой минуте было бы дописано число  1² + 2² + 2²). Докажите, что сотое дописанное число имеет хотя бы 100 различных простых делителей.

Решение

  Пусть S₁, ..., S₁₀₀ – числа, которые были записаны на доске в первые 100 минут. Пусть перед дописыванием числа S_i на доске были числа a₁, ..., a_k. Тогда    а следующее дописанное число  
  Значит, S_i+1 содержит в своем разложении на простые множители все простые числа, на которые делится S_i. Кроме того, поскольку S_i и  S_i + 1  взаимно просты, S_i+1 содержит хотя бы один новый простой множитель (делитель числа  S_i + 1).  Так как  S₁ > 1,  то S₁ содержит в своем разложении хотя бы один простой множитель. Отсюда последовательно получаем, что для  i = 1, 2, ..., 100  число S_i содержит в своем разложении хотя бы i различных простых множителей.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Вариант	2016/2017
этап
Вариант	4
класс
Класс	10
задача
Номер	10.6