Математикадан 40-шы халықаралық олимпиада, 1999 жыл, Бухарест

$n\le 2p$ теңсіздігі орындалатындай және ${{\left( p-1 \right)}^{n}}+1$ саны ${{n}^{p-1}}$ --ге бөлінетіндей барлық $\left( n,p \right)$ натурал сандар жұптарын табыңыздар. Мұндағы $p$ — жай сан.

Комментарий/решение

Заметим, что если $n=1$, то любые значения $p$ подходят.

Пусть $p=2$. Тогда легко проверить, что $n=1,2$. Пусть $p>2$.

Заметим, что тогда $(p-1)^n+1$ нечётное, а значит $n$ тоже нечетное(поэтому $n<2p$). Возьмём наименьший делитель числа $n$. Пусть он равен $q$. Заметим, что $(p-1)^{2n} \equiv 1 \pmod {q}$. Получаем, что показатель числа $(p-1)$ по модулю $q$ равен 2. Отсюда два случая:

1) $p \equiv 0 \pmod {q}$

2) $p \equiv 2 \pmod {q}$

Заметим, что если 2-ой случай выполняется, то $(p-1)^n+1 \equiv 0 \pmod {q}$ ,что невозможно, так как $n$ нечетное. Значит $n=pa$ ,но $n<2p$. Значит $n=p$.

По LTE мы знаем, что степень вхождения числа $p$ в число $(p-1)^p+1$ равно 2, но оно должны быть не меньше чем $p-1$. Отсюда получаем, что $p=3$.

Все ответы: $(1,p),(2,2),(3,3)$