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

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

Условие

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


Решение

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


Ответ

n = 47.

Замечания

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

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

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

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

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