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 \Leftrightarrow a \equiv -1(p^{\alpha})$. We have $a \equiv -1(p)$, hence $a^{p-1} + a^{p-2} + \dots + 1 \equiv p = 0(p)$.
Also $a^p + 1 \equiv (a+1)(a^{p-1} - a^{p-2} + \dots + 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$.
$$(pk-1)^{p-1}-(pk-1)^{p-2}+\dots+1 \equiv (-pk(p-1)+1)-(pk(p-2)-1)+\dots+1 \equiv \\ \equiv -pk \frac{p(p-1)}{2} + p \equiv p(\text{mod } p^2).$$
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 \Leftrightarrow a \equiv -1(q)$ and $a^{p-1} - a^{p-2} + \dots + 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
$$p = \frac{a^p + 1}{a + 1} = a^{p-1} - a^{p-2} + \dots + 1 > a^{p-1} - a^{p-2} = \\ a^{p-2}(a - 1) \geq 3 \cdot 4^{p-2}.$$
Last inequality is impossible. This leads contradiction.