International Zhautykov Olympiad

Let $P(t)$ be the largest prime divisor of a positive integer $t>1$. Let $m$ be the largest odd divisor of $n: n=2^{k} m$. Then $2^{n}+1=2^{2^{k} m}+1=a^{m}+1$, where $a=2^{2^{k}}$. If $k>0$, that is, $n$ is even, then $C(n)=C(m)+2$ and $C(2^{n}+1)=C(a^{m}+1)$. We need the following two lemmas. Lemma 1. For every prime $p>2$ we have $P(\frac{a^{p}+1}{a+1})=p$ or $P(\frac{a^{p}+1}{a+1}) \geqslant 2 p+1$. Proof. Let $P(\frac{a^{p}+1}{a+1})=q$. It follows from Fermat's little theorem that $q$ divides $2^{q-1}-1$ and therefore $(a^{2 p}-1, a^{q-1}-1)=a^{(2 p, q-1)}-1$. The greatest common divisor $(2 p, q-1)$ is even and must equal $2 p$ or 2. In the first case $2 p$ divides $q-1$, whence $q \geqslant 2 p+1$. In the second case $q$ divides $a^{2}-1$ but not $a-1$ (because $a^{p}+1$ is divisible by $q$), that is, $a \equiv-1 \pmod{q}$. Then $\frac{a^{p}+1}{a+1}=a^{p-1}-\ldots+1 \equiv p \pmod{q}$ and $p=q$. Lemma 2. If $p_{1}$ and $p_{2}$ are different odd primes then $P(\frac{a^{p_{1}}+1}{a+1}) \neq P(\frac{a^{p_{2}}+1}{a+1})$. Proof. If $P(\frac{a^{p_{1}}+1}{a+1})=P(\frac{a^{p_{2}}+1}{a+1})=q$ then $q$ divides $a^{2 p_{1}}-1$ and $a^{2 p_{2}}-1$, therefore $(a^{2 p_{1}}-1, a^{2 p_{2}}-1)=a^{(2 p_{1}, 2 p_{2})}-1=a^{2}-1$ and hence $a+1$, but then $p_{1}=q$ and $p_{2}=q$, a contradiction. We are ready now to solve the problem. Let $p_{1}, \ldots, p_{s}$ be all the prime divisors of $n$. It follows from Lemma 2 that $$C(2^{n}+1) \geqslant P(\frac{a^{p_{1}}+1}{a+1})+\ldots+P(\frac{a^{p_{s}}+1}{a+1})$$ If $C(2^{n}+1)>P(\frac{a^{p_{1}}+1}{a+1})+\ldots+P(\frac{a^{p_{s}}+1}{a+1})$, then $2^{n}+1$ has at least one prime divisor not summed in the L.H.S., that is, $$C(2^{n}+1) \geqslant P(\frac{a^{p_{1}}+1}{a+1})+\ldots+P(\frac{a^{p_{s}}+1}{a+1})+3 \geqslant p_{1}+\ldots+p_{s}+3>C(n)$$ Therefore we can assume the equality: $$C(2^{n}+1)=P(\frac{a^{p_{1}}+1}{a+1})+\ldots+P(\frac{a^{p_{s}}+1}{a+1})$$ If in this case there is an $i$ such that $P(\frac{a^{p_{i}}+1}{a+1}) \neq p_{i}$, then $C(2^{n}+1) \geqslant p_{1}+\ldots+p_{s}+p_{i}+1>C(n)$. It remains to consider the case when $P(\frac{a^{p_{i}}+1}{a+1})=p_{i}$ for all $i$. In this case we have $C(n)=C(2^{n}+1)=p_{1}+\ldots+p_{s}$, so $n$ must be odd and $a=2$. But $2^{p} \equiv 2 \pmod{p}$ for all odd prime $p$, therefore $p>3$ cannot divide $2^{p}+1$. Thus $s=1, p=3, n=3^{r}$ with some positive integral $r$. The number $2^{n}+1=2^{3^{r}}+1$ must be a power of 3. However 19 divides this number for $r=2$ and consequently for all $r \geqslant 2$. Thus the only remaining case is $n=3$, which obviously satisfies the condition.