Задача 111346

Темы:    [ Произведения и факториалы ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ Делимость чисел. Общие свойства ]

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

Условие

Автор: Ушаков В. Г.

Найдите наименьшее натуральное n, для которого число nⁿ не является делителем числа 2008!.

Решение

  Если  n ≤ 2008,  то 2008! делится на nⁿ (так как числа n, 2n, ...,  (n – 1)n  и n² содержатся среди чисел 1, 2, ..., 2007, 2008). Так как  44² < 2008 < 45²,  то достаточно проверить делимость 2008! на nⁿ при  n > 45.
  2008! делится на  4545 = 5⁴⁵·3⁹⁰,  так как среди чисел 1, 2, ..., 2007, 2008 заведомо найдётся 45 чисел, кратных 5, и 90 чисел, кратных 3
(5·45 = 22 < 2008  и  3·90 = 270 < 2008).
  2008! делится на  46⁴⁶ = 2⁴⁶·23⁴⁶,  так как среди чисел 1, 2, ..., 2007, 2008 заведомо найдётся 46 чётных чисел и 46 чисел, кратных 23
(23·46 = 1058 < 2008).
  2008! не делится на 47⁴⁷, так как число 47 простое, и поэтому среди чисел 1, 2, ..., 2007, 2008 есть лишь 42 числа, кратных 47
(47·42 = 1974 < 2008 < 2021 = 43·47).

Ответ

n = 47.

Замечания

Для произвольного натурального m наименьшим натуральным n, для которого m! не делится на nⁿ, является наименьшее простое число p, удовлетворяющее неравенству  p² > m.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	71
Год	2008
вариант
Класс	11
задача
Номер	2