Mongolian Mathematical Olympiad

Lemma: Let $p > 2$ be a prime number and $a \in \mathbb{N}$.
(i) $p^{\alpha}|a^p + 1$, $\alpha \ge 1 \Leftrightarrow p^{\alpha+1}|a^p + 1$
(ii) If $a > 2$ then there exist $q > 2$ prime number such that $q|a^p + 1$, $q \nmid a + 1$.
Proof: See 11.6.

If $a = 1$ then above equation has only one solution.
If $a = 2$ then $n > 1$ and $n = p^{\alpha} \cdot n'$, here $p$ is the smallest prime divisor of $n$, $(n', p) = 1$.
Using the lemma, we get $p^{2\alpha}|2^{p^{\alpha} \cdot n'} + 1 \Rightarrow p^{\alpha}|2^{n'} + 1$.
By Euler's theorem
$$\left. \begin{array}{l} p^{\alpha}|4^{p^{\alpha-1}(p-1)} - 1 \\ p^{\alpha}|4^{n'} - 1 \end{array} \right\} \Rightarrow \text{thus } p^{\alpha}|4^{(n',p^{\alpha}(p-1))} - 1 = 3, \text{ hence } \alpha = 3, p = 3.$$

By the Fermat's theorem
$$\left. \begin{array}{l} q|64^{q-1} - 1 \\ q|64^{n'} - 1 \end{array} \right\} \Rightarrow \text{we get that } q|64^{(q-1,n')} - 1 \Rightarrow q|63 \Rightarrow q = 7.$$
But $8^{n'} + 1 \equiv 9 \not\equiv 0 \pmod{7}$ this is contradiction.

The above cases, we get 2 solutions. Let $a + 1 = 2^{\alpha} > 3$ and $p|n$, $p$ is the smallest prime divisor of $n$.
If $p = 2$ then $a^n + 1 \equiv 2 \not\equiv 0 \pmod{4}$. This leads to contradiction.

Hence, we know that $p > 2$ and $p$ is an odd prime number.

$$\left. \begin{array}{l} p|a^{2n} - 1 \\ p|a^{p-1} - 1 \end{array} \right\} \Rightarrow p|a^2 - 1 = a(a - 1)(a + 1) \Rightarrow p|a - 1 \text{ and thus for} \\ a^n + 1 \equiv 2 \not\equiv 0 \pmod{p} \text{ this leads to contradiction.}$$

If there exist $p_1 > 2$ then by Lemma there exist $p_2$ such that $p_1|a+1$, $p_2|a^{p_1+1}$, $p_2|a+1$.
Using Lemma, we have $p_1^2|a^{p_1+1} + 1$ and $p_2|a^{p_1+1} + 1$ from here $p_2^2|a^{p_1p_2+1}$ so on ... $p_1^2...p_k^2|(a^{p_1...p_{k-1}})^{p_k} + 1$, $k \ge 1$.
By the Lemma there exist $p_{k+1}$ prime number such that
$$p_{k+1}|(a^{p_1 \cdots p_{k-1}})^{p_k} + 1, \quad p_{k+1} \nmid a_1^{p_1 \cdots p_{k-1}-1} + 1, \quad p_{k+1} > 2.$$
Also, $(p_{k+1}, p_1...p_{k-1}) = 1$ and if $p_{k+1} = p_k$. Therefore, $p_k^2|(a^{p_1...p_{k-1}})^{p_k} + 1$, thus for if we put there $p_{k+1} = p_k$ then $p_k^2|(a^{p_1...p_{k-1}})^{p_k} + 1 \Rightarrow p_k|a^{p_1...p_{k-1}} + 1$. This leads to contradiction. Thus we can construct infinitely many solutions of mentioned equation.