Решения: Международные олимпиады, Международная Жаутыковская олимпиада (IZHO)

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$ , очевидно, удовлетворяющий условию задачи.

rightways