XVIII математическая олимпиада «Шелковый путь», 2019 год

Найдите все пары $(a,n)$ натуральных чисел таких, что $\varphi (a^n+n)=2^n.$ ($\varphi(n)$ — функция Эйлера, то есть количество целых чисел от 1 до $n$, взаимно простых с $n$.) ( Сатылханов К. )

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

Комментарии от администратора Комментарии от администратора №1.    
Ответ. $(a,n)=(2,1)$, $(3,1),$ $(3,3),$ $(5,1).$
Решение. Рассмотрим несколько случаев:
   i) $a=1.$ В этом случае $\varphi (a^n+n)=\varphi (n+1) < n+1 \le 2^n.$
   ii) $a=2.$ Обозначим $m=2^n+n.$ Если число $m$ простое, тогда $2^n=\varphi (m)=m-1=2^n+n-1,$ откуда $n=1$, что подходит.
   Пусть теперь число $m$ составное и $p$ наименьший его простой делитель, тогда $p \le \sqrt m.$ Так как числа $p,$ $2p,$ $\ldots,$ $\frac{m}{p} \cdot p$ не взаимно просты с $m,$ то $2^n=\varphi (m) \le m-\frac{m}{p} \le m-\sqrt m=2^n+n-\sqrt{2^n+n}.$ Отсюда $2^n+n \le n^2,$ что неверно при натуральном $n$ (индукцией легко доказать обратное неравенство).
   iii) $a \ge 3.$ Обозначим $F_n=2^{2^n}+1$ при $n \ge 0.$
Лемма. Для всех натуральных $n$ выполнено неравенство $\prod\limits_{i = 0}^n {\frac{{{F_i} - 1}}{{{F_i}}}} > \frac{1}{2}.$
Доказательство. Используя тождество $$F_{k+1}-2=2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1)=(F_k-2)F_k$$ получаем, что \[{F_0}{F_1} \ldots {F_n} = ({F_0} - 2){F_0}{F_1} \ldots {F_n} = {F_{n + 1}} - 2 = {2^{{2^{n + 1}}}} - 1.\] Также имеем $$({F_0} - 1)({F_1} - 1) \ldots ({F_n} - 1) = {2^{{2^0}}} \cdot {2^{{2^1}}} \cdot \ldots \cdot {2^{{2^n}}} = {2^{{2^{n + 1}} - 1}},$$ откуда $\prod\limits_{i = 0}^n {\frac{{{F_i} - 1}}{{{F_i}}}} = \frac{{{2^{{2^{n + 1}} - 1}}}}{{{2^{{2^{n + 1}}}} - 1}} > \frac{1}{2}.$ Лемма доказана.
Пусть $a^n+n=2^k p_1^{ \alpha _1 } p_2^{ \alpha _2 } \ldots p_s^{ \alpha _s },$ где $k \ge 0,$ $2 < p_1 < p_2 < \ldots < p_s$ — простые числа и $\alpha _1, \alpha _2, \ldots , \alpha _s$ натуральные числа. Тогда $2^n=\varphi (a^n+n)=2^t p_1^{ \alpha _1-1} p_2^{ \alpha _2-1} \ldots p_s^{ \alpha _s-1} (p_1-1)(p_2-1) \ldots (p_s-1),$ где $t \in \{0, k-1\}.$ Отсюда следует, что $\alpha _1= \alpha _2= \ldots = \alpha _s=1$ и все числа $p_j-1$ степени двоек.
Тогда известно, что существуют целые числа $0 \le i_1 < i_2 < \ldots < i_s$ такие, что $p_j=F_{i_j}$ для каждого $j=1,2, \ldots ,s.$ Из леммы следует, что $$\frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdot \ldots \cdot \frac{p_s-1}{p_s} > \frac{1}{2}. \quad (1)$$
Если $k \ge 1,$ то $\frac{2^n}{a^n+n}=\frac{\varphi (a^n+n)}{a^n+n}=\frac{1}{2} \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdot \ldots \cdot \frac{p_s-1}{p_s} > \frac{1}{4}.$
Если $k =0,$ то $\frac{2^n}{a^n+n}=\frac{\varphi (a^n+n)}{a^n+n}= \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdot \ldots \cdot \frac{p_s-1}{p_s} > \frac{1}{2}.$
В любом случае получаем, что $\frac{2^n}{a^n+n} > \frac{1}{4}$, то есть $$2^{n+2} > a^n+n. \quad (2)$$ Отсюда $4 > {\left( {\frac{a}{2}} \right)^n} \ge {\left( {\frac{3}{2}} \right)^n}$, следовательно $n \le 3.$
Из (2) легко заметить, что при $n=2$ и $n=3$ возможен только случаи $a=3.$ Среди них подходит только пара $(a,n)=(3,3).$
Если $n=1,$ то из (2) следует, что $a < 7.$ Проверкой убеждаемся, что среди них подходит пары $(a,n)=(3,1)$, $(5,1).$

Лемма: Для любого $n\in\mathbf N,\ n\neq 2,6$ верно, что $\varphi(n)\ge \sqrt{n}$.

Ссылка на доказательство

Решение: Рассмотрим случаи:

$1)$ $a^n+n=2\implies (a,n)=(1,1),$ но этот ответ не подходит.

$2)$ $a^n+n=6\implies (a,n)=(1,5),(2,2),(5,1).$ из которых подходят только $\boxed{(5,1)}$

$3)$ $a^n+n\neq 2,6,$ то $4^n=\left(\varphi(a^n+n)\right)^2\ge a^n+n>a^n\implies a\in\{1,2,3\}$

$\mathrm{(i)}$ Случаи $a=1,2$ разобраны в решении админа: $\boxed{(a,n)=(2,1)}$

$\mathrm{(ii)}$ Теперь $a=3.$

$\qquad(1)$ Если $2\mid n,$ то $3^n+n=p_1\dots p_s,$ где $p_1,\dots,p_s\ -$ различные нечетные простые. Тогда

$$\left( \dfrac{2}{3} \right)^n>\dfrac{2^n}{3^n+n}=\dfrac{\varphi(3^n+n)}{3^n+n}=\left(1-\dfrac{1}{p_1}\right)\dots\left(1-\dfrac{1}{p_s} \right)\ge \left( \dfrac{2}{3} \right)^s\implies n<s,$$

$\qquad$тогда $3^n+n\ge 3^s\ge 3^{n+1},$ что невозможно.

$\qquad (2)$ Если $2\nmid n,$ то $3^n+n=2^mp_1\dots p_s,$ где $p_1,\dots,p_s\ -$ различные нечетные простые и $m>0.$ Тогда

$$\left(\dfrac{2}{3}\right)^n>\dfrac{2^n}{3^n+n} = \dfrac{\varphi(3^n+n)}{3^n+n}=\dfrac{1}{2}\left(1-\dfrac{1}{p_1}\right)\dots\left(1-\dfrac{1}{p_s} \right)\ge \dfrac 1 2\cdot \left( \dfrac{2}{3}\right)^s$$

$$\implies \left(\dfrac{2}{3}\right)^{n-s}>\dfrac 1 2\implies n-s\le 1,$$

$\qquad$но с другой стороны $2\cdot 3^n >3^n+n=2^mp_1\dots p_s\ge 2\cdot 3^s\implies n-s>0,$ значит $\boxed{n-s=1}.$

$\qquad$В случае $0\le s\le 2,$ то получаем ответы $\boxed{(a,n)=(3,1),(3,3)}.$ Далее $s\ge 3.$ Заметим, что

$$\left(\dfrac{2}{3}\right)^{s+1}=\left(\dfrac{2}{3}\right)^n>\dfrac{2^n}{3^n+n} = \dfrac{\varphi(3^n+n)}{3^n+n}=\dfrac{1}{2}\left(1-\dfrac{1}{p_1}\right)\dots\left(1-\dfrac{1}{p_s} \right)\ge \dfrac 1 2\cdot \dfrac 2 3\cdot \left(\dfrac{4}{5}\right)^{s-1}$$

$$\implies \dfrac{5^3}{6^3} \ge \left(\dfrac{5}{6}\right)^s>\dfrac{5}{2^3}\implies 5^2>3^3,\ \text{противоречие}.\ \square$$