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

Проект МЦНМО
при участии
школы 57
Задача 116778
Темы:    [ Арифметические функции (прочее) ]
[ Произведения и факториалы ]
[ Делимость чисел. Общие свойства ]
[ Доказательство от противного ]
Сложность: 5-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Автор: Петров Ф.

Для натурального n обозначим  Sn = 1! + 2! + ... + n!.  Докажите, что при некотором n у числа Sn есть простой делитель, больший 102012.


Решение

  Для простого p и натурального n обозначим через vp(n) степень, в которой p входит в разложение n на простые множители. Заметим, что если
vp(n) ≠ vp(k),  то  vp(n + k) = min {vp(n), vp(k)}. Отсюда немедленно следует, что если  vp(Sn) < vp((n + 1)!)  при некотором n, то vp(Sk) = vp(Sn)  при всех  k > n.
  Предположим, что все простые делители чисел вида Sn не превосходят  P = 102012.
  Рассмотрим некоторое простое  pP.  Как показано выше, если  vp(Sn) < vp((n + 1)!)  при некотором n, то существует такое число ap, что  vp(Sk) < ap  при всех натуральных k. Назовём такое простое число p маленьким; все остальные простые числа, меньшие P, назовём большими. Так как маленьких простых конечное количество, существует натуральное M, большее любого числа вида pap, где p – маленькое.
  Пусть теперь p – большое простое число, а n таково, что  n + 2  кратно p. Тогда  vp(Sn+1) ≥ vp((n + 2)!) > vp((n + 1)!);  значит,
vp(Sn) = vp(Sn+1 – (n + 1)!) = vp((n + 1)!) = vp(n!) (поскольку  n + 1  не кратно p).
  Рассмотрим число  N = MP! – 2.  По доказанному,  vp(SN) = vp(N!) для каждого большого простого p. Кроме того, поскольку  N > M,  то
vp(SN) ≤ vp(pap) ≤ vp(N!)  для любого маленького простого p. Поскольку все простые делители числа SN – либо большие, либо маленькие, отсюда следует, что  SN ≤ N!.  Противоречие.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2011-2012
Этап
Вариант 5
класс
Класс 11
Задача
Номер 11.8

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

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