Найти число

[Бином]

Вот нашел задачку с Московской олимпиады для школьников. Прошу проверить мой ответ.

Задача №2. Найдите наименьшее натуральное n, для которого число n^n не является делителем числа 2008!=1· 2·...· 2008.

Я думаю, что это число равно 2009, но я не могу доказать это.

[Профессор Снэйп]

Бином писал(а):

Вот нашел задачку с Московской олимпиады для школьников. Прошу проверить мой ответ.

Задача №2. Найдите наименьшее натуральное n, для которого число n^n не является делителем числа 2008!=1· 2·...· 2008.

Я думаю, что это число равно 2009, но я не могу доказать это.

То есть Вы хотите сказать, что число $2008^{2008}$ делит $2008!$. Сами-то понимаете, насколько это абсурдно выглядит?

[Бином]

Да, это я перебрал:). Думаю надо просмотреть все числа 2^2, 3^3, 4^4... и первое число n, n^n, которого ,будет больше 2008 будет этим числом.

[scorpio]

47

[Профессор Снэйп]

Бином писал(а):

Да, это я перебрал:). Думаю надо просмотреть все числа 2^2, 3^3, 4^4... и первое число n, n^n, которого ,будет больше 2008 будет этим числом.

Почему это Вам такие глупости в голову лезут?

[Someone]

Рассмотрите разложение числа $2008!$ и чисел $n^n$ на простые множители.

[TOTAL]

$47^2 > 2008$, поэтому $47^{47}$ не делит $2008!$
$44^2 < 2008$, поэтому $n^n$ делит $2008!$ при $n \le 44$
Остается проверить и отвергнуть 45 и 46

[General]

Да, точно!
Рассмотрим сначала простые n. Чтобы найти, в какой степени простое число n входит в 2008! нужно найти сумму $\left[\frac{2008}{n}\right]+\left[\frac{2008}{n^2}\right]+\left[\frac{2008}{n^3}\right]+...$
Для n=47 данная сумма будет равна 42 (уже второе слагаемое будет 0, всё, понял почему вы в квадрат возводите)

Ну а для составных 44, 45, 46 нужно проверять степени вхождение максимального простого множителя, а те входить будут.