13-я Международная Жаутыковская олимпиада, 2017 год

Для каждого натурального $k$ обозначим через $C(k)$ сумму всех различных простых делителей числа $k$. Например, $C(1)=0$, $C(2)=2$, $C(45)=8$. Найдите все натуральные $n$, для которых $C(2^n+1)=C(n)$. ( Н. Седракян )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ: $n=3$.
Решение. Для каждого натурального $t > 1$ обозначим $P(t)$ наибольший простой делитель числа $t$.
Выделим из натурального $n$ наибольший нечётный делитель: $n=2^km$. Тогда, $2^n+1=2^{2^km}+1=a^m+1$, где $a=2^{2^k}$. Если $k > 0$, то есть $n$ чётно, то $C(n)=C(m)+2$, а $C(2^n+1)=C(a^m+1)$.
Докажем следующие леммы.
Лемма 1. При каждом простом $p > 2$ имеем $P\left({a^p+1\over a+1}\right)=p$ или $P\left({a^p+1\over a+1}\right)\geq 2p+1$.
Доказательство. Пусть $P\left({a^p+1\over a+1}\right)=q$. По малой теореме Ферма $q$ делит $2^{q-1}-1$, следовательно, и $(a^{2p}-1, a^{q-1}-1)=a^{(2p, q-1)}-1$. Наибольший общий делитель $(2p, q-1)$ чётен и, следовательно, равен $2p$ или 2. В первом случае $q-1$ кратно $2p$, откуда $q\geq 2p+1$. Во втором случае $a^2-1$ кратно $q$, но $a-1$ не кратно $q$ (так как $a^p+1$ кратно $q$), то есть $a\equiv -1\pmod q$. Тогда ${a^p+1\over a+1}=a^{p-1}-\dots+1\equiv p\pmod q$. то есть $p=q$.
Лемма 2. Если $p_1$ и $p_2$ — различные нечётные простые числа, то $P\left({a^{p_1}+1\over a+1}\right)$ не равно $P\left({a^{p_2}+1\over a+1}\right)$.
Доказательство. Если $P\left({a^{p_1}+1\over a+1}\right)=P\left({a^{p_2}+1\over a+1}\right)=q$, то оба числа $a^{2p_1}-1$ и $a^{2p_2}-1$ кратны $q$, следовательно, на $q$ делится $(a^{2p_1}-1, a^{2p_2}-1)=a^{(2p_1, 2p_2)}-1=a^2-1$ и, значит, $a+1$, но тогда $p_1=q$ и $p_2=q$ — противоречие.
Перейдём теперь к решению задачи. Пусть $n$ имеет нечётные простые делители $p_1$, $\ldots$, $p_s$. По лемме 2 имеем $$C(2^n+1)\geq P\left({a^{p_1}+1\over a+1}\right)+\dots +P\left({a^{p_s}+1\over a+1}\right)$$ Если $C(2^n+1) > P\left({a^{p_1}+1\over a+1}\right)+\dots +P\left({a^{p_s}+1\over a+1}\right)$, то у $2^n+1$ есть ещё хотя бы один простой делитель, кроме сложенных в правой части, то есть $$C(2^n+1)\geq P\left({a^{p_1}+1\over a+1}\right)+\dots +P\left({a^{p_s}+1\over a+1}\right)+3\geq p_1+\dots+p_m+3 > C(n).$$ Поэтому достаточно разобрать случай равенства: $$C(2^n+1)=P\left({a^{p_1}+1\over a+1}\right)+\dots +P\left({a^{p_s}+1\over a+1}\right).$$ Если в этом случае существует $i$, для которого $P\left({a^{p_i}+1\over a+1}\right)\ne p_i$, то $C(2^n+1)\geq p_1+\dots+p_m+p_i+1 > C(n)$.
Осталось рассмотреть ситуацию, когда $P\left({a^{p_i}+1\over a+1}\right)=p_i$ при всех $i$. В ней имеем $C(n)=C(2^n+1)=p_1+\dots+p_s$, поэтому $n$ нечётно и $a=2$. Но $2^p\equiv 2\pmod p$ при всех нечётных $p$, поэтому при $p > 3$ число $2^p+1$ не кратно $p$. Таким образом, $s=1$, $p=3$, $n=3^r$ с некоторым натуральным $r$. Тогда число $2^n+1=2^{3^r}+1$ должно быть степенью тройки. Однако уже при $r=2$ и, следовательно, при всех $r\geq 2$ это число кратно 19. Таким образом, остаётся только случай $n=3$, очевидно, удовлетворяющий условию задачи.

Похожие задачи:

http://matol.kz/comments/605/show

http://matol.kz/comments/743/show

http://matol.kz/comments/795/show