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

Проект МЦНМО
при участии
школы 57
Задача 66023
Темы:    [ Последовательности (прочее) ]
[ Основная теорема арифметики. Разложение на простые сомножители ]
[ НОД и НОК. Взаимная простота ]
Сложность: 3+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

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

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

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

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

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