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).$