45th 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\iff 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^{\prime }$, here $p$ is the smallest prime divisor of $n$, $(n^{\prime },p)=1$. Using the lemma, we get $p^{2\alpha }|2^{p^{\alpha }\cdot n^{\prime }}+1\Rightarrow p^{\alpha }|2^{n^{\prime }}+1$. By Euler's theorem $$\begin{array}{l}{p}^{\alpha }|4^{p^{\alpha -1}(p-1)}-1\\ p^{\alpha }|4^{n^{\prime }}-1\end{array}\}\Rightarrow \text{thus }{p}^{\alpha }|4^{(n^{\prime },p^{\alpha }(p-1))}-1=3,\text{ hence }\alpha =3,p=3.$$

By the Fermat's theorem $$\begin{array}{l}q|64^{q-1}-1\\ q|64^{n^{\prime }}-1\end{array}\}\Rightarrow \text{we get that }q|64^{(q-1,n^{\prime })}-1\Rightarrow q|63\Rightarrow q=7.$$ But $8^{n^{\prime }}+1\equiv 9\not\equiv 0(\mathrm{mod}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(\mathrm{mod}4)$. This leads to contradiction.

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

$$\begin{gathered} \begin{array}{l}p|a^{2n}-1\\ p|a^{p-1}-1\end{array}\}\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(\mathrm{mod}p)\text{ this leads to contradiction.} \end{gathered}$$

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_1{p}_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,p_{k+1}\nmid a_1^{p_1\cdots p_{k-1}-1}+1,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.