Найти наименьшее натуральное $%n$%, при котором $%n^n$% не является делителем $%2013!=1\cdot2\cdot3\cdot\ldots\cdot2013$%.

задан 27 Авг '13 13:33

изменен 30 Авг '13 14:37

falcao's gravatar image


183k1632

10|600 символов нужно символов осталось
2

Разложение числа $%n!$% в произведение степеней простых чисел выглядит, как известно, следующим образом: показатель степени при простом числе $%p$% вычисляется по формуле $$\nu_p=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots.$$ Начать можно с того, чтобы подобрать такое простое $%p$%, при котором означенный показатель степени будет больше $%p$% (далее полагаем $%n=2013$%). Легко понять, что с увеличением $%p$% показатель $%\nu_p$% не может увеличиться. Чтобы не проверять все $%p$%, можно начать со значений, близких к $%\sqrt{n}$%. Прямой подсчёт показывает, что $%\nu_{43}=47$%, и $%\nu_{47}=42$%. Отсюда ясно, что $%2013!$% не делится на $%47^{47}$%, и остаётся проверить, что число $%47$% является наименьшим из чисел с таким свойством.

Пусть $%k\le46$%; мы хотим проверить, что $%2013!$% делится на $%k^k$%. Для этого достаточно убедиться в следующем: если $%k$% делится на $%p^m$%, где $%p$% простое, $%m\ge1$%, то $%2013!$% делится на $%p^{46m}$%, а потому и на $%p^{km}$%. При $%m=1$% это очевидно, так как все числа $%\nu_p$% при простых $%p < 47$%, как мы уже знаем, не меньше $%\nu_{43}=47$%. Если $%m\ge2$%, то $%46\ge p^2$%, откуда $%p=2,3,5$%. Это всего три случая, и для них показатели $%\nu_p$% легко подсчитать. В частности, все они больше $%500$%, а показатель $%m$% всегда не больше пяти (так как $%2^6$% уже больше $%46$%). Отсюда ясно, что $%2013!$% будет делиться даже на $%p^{100m}$% при этих значениях $%p$%.

ссылка

отвечен 27 Авг '13 14:21

спасибо большое!

(30 Авг '13 1:16) ridick
10|600 символов нужно символов осталось
0

Первое простое, больше корня из 2013. Вроде очевидно...

ссылка

отвечен 3 Сен '13 2:53

Но тут ещё надо проверить, что для всех меньших составных чисел делимость будет иметь место. Это не столь очевидно. Скажем, если $%p$% -- простое число, описанное выше, то как доказать, что $%n!$% будет делиться, например, на $%(p-1)^{p-1}$%? Боюсь, что в общем случае это вообще неверно. Например, при $%n=9$% получается $%p=5$%, однако наименьшим здесь будет не $%5$%, а $%4$%, так как $%9!$% не делится на $%4^4$%.

(3 Сен '13 12:42) falcao

Это более чем очевидно. В списке 1,.....,n*n встретится как минимум n, 2n, 3n.... - т.е. кратных числу n. И это для любого делителя числа, меньшего указанного.

(3 Сен '13 14:17) behemothus

Про те числа, которые меньше корня, все ясно. @falcao говорит о том, что решение может и не быть простым числом.

(3 Сен '13 14:35) DocentI

@behemothus: если $%k\le\sqrt{n}$%, то я согласен с тем, что $%n!$% будет делиться на $%k^k$%. Но этого недостаточно: когда выбрано наименьшее простое $%p$%, большее корня из $%n$%, остаются ещё составные числа (строго) между $%\sqrt{n}$% и $%p$%. См. также случай $%n=9$%, для которого я привёл контрпример.

(3 Сен '13 14:50) falcao

falcao, любой простой делитель составного числа, меньшего 2n, меньше n. Надо доказывать, что 46/2 меньше корня из 2013???

(3 Сен '13 16:01) behemothus

@behemothus: если Вы говорите о случае числа $%2013!$%, как в исходной задаче, то здесь проверке подлежат всего два числа: $%45$% и $%46$% -- поскольку $%44^2 < 2013$%. Проверка для каждого из этих чисел действительно лёгкая. Но если говорить про общий случай, то там уже совсем не очевидно, что такой подход сработает. Моё замечание относилось к произвольному простому $%p$%, а не к случаю $%p=47$%. (Кстати говоря, если быть формально точным, то простой делитель числа $%2n$% может быть и равен $%n$%, но это уже как бы "к слову".)

(3 Сен '13 17:46) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×175

задан
27 Авг '13 13:33

показан
881 раз

обновлен
3 Сен '13 17:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru