Республиканская олимпиада по математике, 2014 год, 11 класс

Существуют ли натуральные числа $a$ и $b$ такие, что для каждого натурального $n$ числа ${{a}^{n}}+{{n}^{b}}$ и ${{b}^{n}}+{{n}^{a}}$ взаимно просты? ( Сатылханов К. )

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

Комментарии от администратора Комментарии от администратора №1.     Предположим, что существуют такие числа $a$ и $b$. Если $(a,b)=d>1$, то достаточно взять $n=d$, и тогда числа ${{a}^{n}}+{{n}^{b}}$ и ${{b}^{n}}+{{n}^{a}}$ не будут взаимно простыми. Поэтому $(a,b)=1$. Пусть $p$ — простой делитель числа $a^a+b^b$. Не теряя общность положим, что $a \geq b$. Тогда существует целое число $k$ такое, что $1 \leq k \leq p-1$ и $k \equiv \dfrac{b}{a} \pmod p$. Возьмем натуральное число $n=k+p\cdot (a-b-k+p-1)$. Тогда $${a^n} + {n^b} \equiv {a^k} \cdot {a^{p \cdot (a - b - k + p - 1)}} + {k^b} \equiv {a^k} \cdot {a^{a - b - k + p - 1}} + {k^b} \equiv $$ $$\equiv {a^{a - b}} \cdot {a^{p - 1}} + {k^b} \equiv {a^{a - b}} + {\left( {\frac{b}{a}} \right)^b} \equiv \frac{{{a^a} + {b^b}}}{{{a^b}}} \equiv 0 \pmod p.$$ Аналогично имеем \[{b^n} + {n^a} \equiv {b^{a - b}} + {\left( {\frac{b}{a}} \right)^a} \equiv \frac{b^{a-b}({{a^a} + {b^b}})}{{{a^a}}} \equiv 0 \pmod p .\] Получается, что $1 = \left( {{a^n} + {n^b},{b^n} + {n^a}} \right) \vdots p$, что невозможно.