Задача на делимость

[maxmatem]

Вот очень понравилась задача.

Найти наименьшее натуральное число $n$, такое что число $n^{n}$ не делит $2010!$

[venco]

Уже было: topic22807.html

(Оффтоп)

Поиск по формулам рулит.

[maxmatem]

venco
извиняюсь.........

[nnosipov]

Раз уж снова заговорили об этой задаче, кое-что добавлю (кажется, в топике, указанном venco, это не обсуждалось). В брошюре http://olympiads.mccme.ru/mmo/2008/solutions.pdf на стр. 33 читаем:

"Легко заметить, что для произвольного натурального $x$ наименьшим натуральным $n$, для которого $x!$ не делится на $n^n$, является наименьшее простое число $p$, такое, что $p^2>x$."

Пробую "легко заметить", но ничего не выходит. Через некоторое время вообще обнаруживается контрпример: $x=9$. В итоге утверждение всё же спасается заменой "произвольного" на "достаточно большого", но при доказательстве приходится применять теорему Чебышёва. В связи с этим вопрос: есть ли ещё контрпримеры и какова та граница, начиная с которой всё будет OK? Если этот вопрос ранее обсуждался, подскажите где.

[RIP]

Перебор на компьютере показывает, что $x=9$ --- единственный контрпример.

[nnosipov]

RIP в сообщении #442407 писал(а):

Перебор на компьютере показывает, что $x=9$ --- единственный контрпример.

А границы перебора каковы?

[RIP]

До $x=169$. Пусть $x\ge169$. Тогда проверяем, что $n>16$. Допустим, что $n$ составное, $n=p^\alpha m$, где $(m,p)=1$, $\nu_p(n^n)>\nu_p(x!)$. Тогда $p^2\le x$ (иначе $n$ не минимально), поэтому $\nu_p(x!)\ge\lfloor x/p\rfloor+1>x/p$, то есть $\alpha pn>x$. Если $\alpha\ge2$, то $p\le n^{1/2}$ и $\alpha p\le\frac{p\log n}{\log p}\le2n^{1/2}\le n/2$ (напомню, что $n\ge16$). Если $\alpha=1$, то неравенство $\alpha p\le n/2$ тоже очевидно. В любом случае получаем неравенство $n>\sqrt{2x}$. Осталось доказать, что для любого $x\ge169$ на промежутке $(\sqrt x,\sqrt{2x}]$ всегда есть простое число. Это правда, но ссылку дать не могу.

[nnosipov]

RIP в сообщении #442466 писал(а):

До $x=169$. Пусть $x\ge169$. Тогда проверяем, что $n>16$. Допустим, что $n$ составное, $n=p^\alpha m$, где $(m,p)=1$, $\nu_p(n^n)>\nu_p(x!)$. Тогда $p^2\le x$ (иначе $n$ не минимально), поэтому $\nu_p(x!)\ge\lfloor x/p\rfloor+1>x/p$, то есть $\alpha pn>x$. Если $\alpha\ge2$, то $p\le n^{1/2}$ и $\alpha p\le\frac{p\log n}{\log p}\le2n^{1/2}\le n/2$ (напомню, что $n\ge16$). Если $\alpha=1$, то неравенство $\alpha p\le n/2$ тоже очевидно. В любом случае получаем неравенство $n>\sqrt{2x}$. Осталось доказать, что для любого $x\ge169$ на промежутке $(\sqrt x,\sqrt{2x}]$ всегда есть простое число. Это правда, но ссылку дать не могу.

Прелестно, у меня как раз такой же интервал $(\sqrt x,\sqrt{2x}]$ вылез.