Теория чисел

[maxmatem]

Найти все пары $(n;p)$ натуральных чисел такие, что $p$-простое , $n \leq 2p$ и $(p-1)^{n}+1$ делится на $n^{p-1}$

[nnosipov]

Эта задача с 40-й IMO. Здесь можно убрать условие $n \leqslant 2p$, ответ не изменится.

[maxmatem]

nnosipov
да да с неё, просто задача понравилась, вот и решил поделиться, а про убирание условия не знал, спс

[Dendr]

Вроде можно и требование простоты $p$ убрать. Достаточно $p>1$.

[maxmatem]

Dendr
вот что то я не уверен..... вряд ли на межнар дали бы задачу с такими гибкими условиями

[nnosipov]

Dendr в сообщении #1533995 писал(а):

Вроде можно и требование простоты $p$ убрать.

Как-то это неочевидно. У Вас есть доказательство?

[maxmatem]

я уверен что простоту p убирать не в кое случаи нельзя

[Dendr]

Действительно, нельзя. Помутнение нашло - решил, что в МТФ идет речь о взаимной простоте.

А в целом вот что: ясно, что есть тривиальные решения $(1, p), (n, 1)$. Пары $(2, 2), (3, 3)$ нетрудно найти даже руками.
Так же легко установить, что $n$ не может быть четным (кроме уже приведенных случаев) - случай $q=1$ дает $n=1, n=2$, в остальных случаях $q^n+1=(q^{n/2})^2+1$ должно делиться на 4, но это невозможно.

Далее можно заметить, что (обозначая $q=p-1$) либо $n^q-q^n=1$, либо $n^q<q^n$. Первое уравнение имеет только два решения, которые уже указаны выше. (надо ли здесь специально доказывать?)
Из второго неравенства следует, что $\frac{\ln n}{n}<\frac{\ln q}{q}$. Поскольку мы рассматриваем теперь только $n\ge3$, то получаем $q<n$. Или $p\le{n}$. Добавим также, что $n, q$ должны быть взаимно просты.

Вот здесь я и допустил ошибку: если бы МТФ была верна для таких случаев, то $q^n\equiv{q} \mod{n}$, то есть должно выполняться, по крайней мере, $n|q+1$, значит, единственная возможность - $q=n-1$. Но (помним про нечетность) $(n-1)^n+1=n^n-n\cdot n^{n-1}+... -\frac{n(n-1)}{2}n^2+n\cdot n-1+1$ - делится на $n^2$, но не на $n^3$. Поэтому $q\le2$, и мы приходим все к тем же решениям, а других решений больше нет.

На самом деле это, конечно, не так: например, уже $2^9\equiv8\neq2\mod{9}$, и "подходящих" значений $q$ может быть больше. Тогда нельзя из сравнительно простых соображений исключить, что еще решения есть.

Как применить ограничение на простоту $p$, пока не сообразил.

[Dendr]

А, ну конечно. Все гораздо проще. Рассматриваем только нечетные $n$, тогда, по условию, выполняется, крайней мере,

$$n|(p-1)^n+1=p^n-np^{n-1}+\frac{n(n-1)}{2}p^{n-2}+...-\frac{n(n-1)}{2}p^2+np-1+1$$

Из этого следует, что $n|p^n$. Следовательно, $n$ - некоторая степень $p$. Пусть $n=p^k$.
Тогда получаем

$$p^{k(p-1)}|(p-1)^{p^k}+1=p^{p^k}-p\cdot p^{p^k-1}+...-\frac{p^{k}\cdot \left(p^{p^k}-1\right)}{2}p^2+p^{k}\cdot p-1+1$$

Наименьшая степень $p$ справа - $k+1$, следовательно, $k(p-1)\le{k+1}, k(p-2)\le1$.
Отсюда, либо $k=0$ (тривиальное решение $n=1$), либо $p=2$ (это можно подставить непосредственно в условие и получить $n|2$, но новых решений это - пока - не даст), либо $p=3, k=1 \Rightarrow n=3$.

Если же $n$ - четное, то $(p-1)^n$ - нечетное. Следовательно, $p$ - четное, то есть $p=2$, и снова $n|2$, откуда получаем пару $(2, 2)$.

Ответ: $(1, p), (2, 2), (3, 3)$

[nnosipov]

Dendr в сообщении #1534264 писал(а):

Из этого следует, что $n|p^n$.

Как именно следует?