Делимость $(p-1)^n+1$ на $n^{p-1}$

[nnosipov]

Пусть $p$ --- нечётное простое, $n>1$ --- натуральное. Когда $(p-1)^n+1$ делится на $n^{p-1}$? На 40-й IMO этот вопрос был задан в урезанной форме: дополнительно предполагалось, что $n \leqslant 2p$.

[Sonic86]

(решающим сюда не смотреть!)

:D решил с помощью 3-х английских букв, недавно упоминавшихся. Задача не усложнилась даже. После попыток народа выложу ссылку, если Вы сами не имели ввиду ее.

[nnosipov]

Sonic86 в сообщении #469655 писал(а):

(Оффтоп)

... решил с помощью 3-х английских букв ...

(Оффтоп)

LTE. Хорошо, что не с помощью 3-х русских

[maxal]

Во-первых, заметим, что $n$ обязано быть нечетно.

Пусть $q$ - наименьший простой делитель числа $n$. Тогда мультипликативный порядок $\mathrm{ord}_q(p-1)$ (который строго меньше $q$) делит $2n$. В виду минимальности выбора $q$ получаем, что $\mathrm{ord}_q(p-1)$ равен 1 или 2. Однако 1 он равен быть не может (в этом случае $q$ делило бы $p-2$ и $p$, что невозможно), поэтому $\mathrm{ord}_q(p-1)=2$, а значит, $q$ делит $p(p-2)$, но не $p-2$. Отсюда немедленно получаем, что $q=p$.

Пусть $\nu_{p}(n)=k\geq 1$. Тогда $\nu_p( (p-1)^n+1) = 1+k$ и должно выполняться неравенство:

$$1+k \geq k(p-1)$$

откуда $p=3$ и $k=1$.

Таким образом, задача сводится к нахождению всех таких $n$, что $2^n+1$ делится на $n^2$. Однако в данном случае как легко убедится другого простого, кроме 3, делящего $n$ не существует. Поэтому $n=3$ - единственное решение.

[nnosipov]

Забавное обстоятельство: задача про делимость $2^n+1$ на $n^2$ --- с 31-й IMO.