45th Mongolian Mathematical Olympiad

To prove this problem we need following lemma.

Lemma. Let $2<p$-prime number. (i) If $\alpha \in \mathbb{N}$ then $p^{\alpha }|a+1$ if and only if $p^{\alpha +1}|a+1$. From here, we get $p^2\nmid \frac{a^p+1}{a+1}$. (ii) If $a\ge 4$ integer then there exist $q$ prime number such that $q|\frac{a^p+1}{a+1}$ and $q\nmid a+1$. Proof of (i). $p^{\alpha }|a+1\iff a\equiv -1(p^{\alpha })$. We have $a\equiv -1(p)$, hence $a^{p-1}+a^{p-2}+\cdots +1\equiv p=0(p)$. Also $a^p+1\equiv (a+1)(a^{p-1}-a^{p-2}+\cdots +1)$, so $p^{\alpha +1}|a^p+1$. Let $a^p\equiv -1(\text{mod }{p}^{\alpha +1})$. By Fermat's theorem $a^p\equiv p\equiv 1(p)$. Thus $a=pk-1$. $$\begin{gathered} (pk-1{)}^{p-1}-(pk-1{)}^{p-2}+\cdots +1\equiv (-pk(p-1)+1)-(pk(p-2)-1)+\cdots +1\equiv \\ \equiv -pk\frac{p(p-1)}{2}+p\equiv p(\text{mod }{p}^2). \end{gathered}$$ In other words that ${\text{ord}}_p\left(\frac{a^p+1}{a+1}\right)=1$. Thus $p\alpha |a+1$ but $p^2\nmid \frac{a^p+1}{a+1}$. Proof of (ii). If for every $q\in \mathbb{N}:q|\frac{a^p+1}{a+1}$ then $q|a+1\iff a\equiv -1(q)$ and $a^{p-1}-a^{p-2}+\cdots +1\equiv p\equiv 0(q)$. From here we have $q=p$. Hence $p^{\alpha }=\frac{a^p+1}{a+1}$. By using (i) we get $$\begin{gathered} p=\frac{a^p+1}{a+1}=a^{p-1}-a^{p-2}+\cdots +1>a^{p-1}-a^{p-2}= \\ {a}^{p-2}(a-1)\ge 3\cdot 4^{p-2}. \end{gathered}$$ Last inequality is impossible. This leads contradiction.