Азиатско-Тихоокеанская математическая олимпиада, 2012 год

Определите всевозможные пары $(p, n)$ простого числа $p$ и натурального числа $n$, для которых $\dfrac{{{n^p} + 1}}{{{p^n} + 1}}$ — является целым.

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

Ответ:$(n,p)=(2,2),(4,2),(q,q),\forall q\in\mathbb P_{>2}$

Если $p=2$, то $n^2\ge 2^n\implies n=2,3,4$, но только $n=3$ не подходит.

Далее $p\ge 3$. Тогда $2\mid p^n+1\mid n^p+1$, откуда $2\nmid n$.

Если $n=1$, то $p+1\mid 2$, что невозможно. Далее $n\ge 3$.

Из условия получаем, что $n^p\ge p^n$, откуда $n\le p$.

Случай $n=p$ подходит под условие задачи, далее $n< p$.

Заметим, что $p+1\mid p^n+1$ $$\implies p+1\mid n^p+1\mid n^{2p}-1\quad (\color{red}1)$$

Пусть $p+1=2^ap_1^{a_1}...p_s^{a_s},\quad p_i\in\mathbb P; a,a_i\in\mathbb N, \forall 1\le i\le s$

Легко понять, что $(p,p_i)=(p,p_i-1)=(p,2)=1\quad (\mathrm i)$

так как $p>p_i,\forall 1\le i\le s$

По теореме Эйлера: $$p+1\mid n^{φ(p+1)}-1=n^{2^{a-1}p_1^{a_1-1}... p_s^{a_s-1}(p_1-1)...(p_s-1)}-1\quad(\color{red}2)$$

Пусть $d$ - наименьшее число такое, что $$p+1\mid n^d-1$$

Тогда из $(\color{red}1)$ и $(\color{red}2)\implies d\mid 2p$ и $d\mid φ(p+1)$

Из $(\mathrm i)$ следует, что $(φ(p+1),p)=1$, откуда $d\mid 2\implies p+1\mid n^2-1=(n-1)(n+1)$

Пусть $(p+1,n-1)=k$, тогда из $(\color{red}1)$ получаем, что $k\mid n^p+1\equiv 1^p+1=2\pmod k\implies k\mid 2$

Откуда $p+1\mid 2(n+1)<2(p+1)$,

значит $p+1=2(n+1)\implies 2n+1=p$

Отметим, следующее

$v_2(n+1)=v_2(n^p+1)\ge v_2(p^n+1)=v_2(p+1)=v_2(2(n+1))=$

$=1+v_2(n+1)\implies 0\ge 1,$ что невозможно.

Для $p=2$ сделан разбор сверху, теперь скажем что это число нечетное и простое, тогда и $n$ нечётно. $n^p\geq p^n$ Возьмём оба выражения под корень силы $pn$ $\rightarrow n^{1/n}\geq p^{1/p}$, кстати функция $x^{1/x}$ убывающая так что $p\geq n.$

$p+1 |p^n+1 |n^p+1(p^n+1=(p+1)(…))$ $(p-odd).$

$n^p \equiv -1 (mod$ $p+1)$ $\rightarrow n^{2p} \equiv 1(p+1)$ Значит показатель равен $2$ или $2p$. Второй вариант невозможен ибо $2p > p+1>$ функция эйлера от $p+1$. Значит $n^q \equiv -1(p+1)$ (где $q$ нечётно), $p+1|n+1$ и $n \geq p$.

Ответы: $\boxed{n=p; n=4,p=2; p=2, n=2!}$

Докажем что $a^b>b^a$ при $b>a\geq 3$

Для этого достаточно показать что $n^{n+1} \geq (n+1)^n$, то есть $n^n*(n-1) \geq \sum n^{n-i}*C_{n}^{i}$, применим факт что $C_{n}^{i} \leq n^i$ для $i=1,2,...,n-2$. Осталось доказать что $n^n> n+1$ что правда при $n\geq 3$.

$p=4$ не решение т.к. $p$ простое