|
Найти наименьшее натуральное $%n$%, при котором $%n^n$% не является делителем $%2013!=1\cdot2\cdot3\cdot\ldots\cdot2013$%. задан 27 Авг '13 13:33 
ridick |
|
Разложение числа $%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 
falcao спасибо большое!
(30 Авг '13 1:16)
ridick
|
|
Первое простое, больше корня из 2013. Вроде очевидно... отвечен 3 Сен '13 2:53 
behemothus Но тут ещё надо проверить, что для всех меньших составных чисел делимость будет иметь место. Это не столь очевидно. Скажем, если $%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
|