Serbian Mathematical Olympiad

Solution:

If $n=\prod_{i=1}^{k} p_{i}^{r_{k}}$ is the canonical factorization of $n$, then $\varphi(n)=\prod_{i=1}^{k} p_{i}^{r_{k}-1}\left(p_{i}-1\right)$ holds, so since $n$ has no prime factors other than two, it must be that $a_{i}=1$ and $p_{i}-1=2^{b_{i}}$ for every $i$ and some $b_{i}$. Since $2^{b_{i}}+1$ can be prime only if $b_{i}$ is a power of two, we have $p_{i}=2^{2^{c_{i}}}+1$ for some distinct $c_{i}$.

Suppose that $n+1$ is not a power of two. From the fact that $\varphi(n+1)$ is a power of two we obtain that all odd prime divisors of $n+1$ are of the form $2^{2^{d_{i}}}+1$. Therefore,
$$n=\prod_{i=1}^{k}\left(2^{2^{c_{i}}}+1\right), \quad n+1=2^{t} \prod_{j=1}^{l}\left(2^{2^{d_{j}}}+1\right)$$
where all $c_{i}$ and $d_{j}$ are mutually distinct. We may assume without loss of generality that $c_{1}<\cdots<c_{k}$ and $d_{1}<\cdots<d_{l}$.

For every $m, M \in \mathbb{N}, m \leq M$, by simple induction one shows that
$$\frac{2^{2^{m}}+1}{2^{2^{m}}}<\prod_{i=m}^{M} \frac{2^{2^{i}}+1}{2^{2^{i}}}=\frac{2^{2^{m}}}{2^{2^{m}}-1} \cdot \frac{2^{2^{M+1}}-1}{2^{2^{M+1}}}<\frac{2^{2^{m}}}{2^{2^{m}}-1}$$
From this we obtain
$$\frac{2^{2^{c_{1}}}+1}{2^{2^{c_{1}}}} 2^{c} \leqslant n<\frac{2^{2^{c_{1}}}}{2^{2^{c_{1}}}-1} 2^{c} \quad \text{and} \quad \frac{2^{2^{d_{1}}}+1}{2^{2^{d_{1}}}} 2^{d} \leqslant n+1<\frac{2^{2^{d_{1}}}}{2^{2^{d_{1}}}-1} 2^{d}$$
where $c=\sum_{i} 2^{c_{i}}$ and $d=t+\sum_{j} 2^{d_{i}}$. It follows that $c=d$. If $d_{1}>c_{1}$, then $\frac{2^{2^{d_{1}}}}{2^{2^{d_{1}}}-1}<\frac{2^{2^{c_{1}}}+1}{2^{2^{c_{1}}}}$ holds, so $n+1<n$, a contradiction. Therefore, $d_{1}<c_{1}$, and then $n+1 \geqslant \frac{2^{2^{d_{1}}}+1}{2^{2^{d_{1}}}} 2^{c}>\frac{2^{2^{c_{1}}}}{2^{2^{c_{1}}}-1} 2^{c}>n$, so $\frac{n+1}{n}>\frac{2^{2^{d_{1}}}+1}{2^{2^{d_{1}}}} \cdot \frac{2^{2^{c_{1}}}-1}{2^{2^{c_{1}}}}$ and, because of $n \geqslant 2^{2^{c_{1}}}+1 \geqslant a^{2}+1$ for $2^{2^{d_{1}}}=a, \frac{n+1}{n}>\frac{(a+1)\left(a^{2}-1\right)}{a^{3}}=1+\frac{a^{2}-a-1}{a^{3}}$, from which we conclude $a^{2}+1 \leqslant n<\frac{a^{3}}{a^{2}-a-1}$. The only possibility is $a=2$ and $n=5$.