Brazilian Mathematical Olympiad

Let $q$ be an odd prime and take $n + 1 = q^{2^k}$. Then $p(q^{2^k}) = q$. Since $\gcd(q^{2^k} + 1, q^{2^l} + 1) = 2$ for $k \neq l$ (indeed, if $d$ is such $\gcd$ and $k < l$,

$$q^{2k} \equiv -1 \pmod d \implies q^{2l} \equiv 1 \pmod d \iff d \mid 2$$

$p(q^{2k} + 1)$ can be arbitrarily large. So let $k$ be the least integer value such that $p(q^{2k} + 1) > q$. Hence all prime divisors of $q^{2t} + 1$, $t < k$, are smaller than $q$. Since $q^{2k} - 1 = (q-1)(q+1)(q^2+1)\cdots(q^{2k-1}+1)$ and $q-1 < q$, all prime divisors of $q^{2k} - 1$ are smaller than $q$, so $p(q^{2k} - 1) < q$. So $p(q^{2k} - 1) < p(q^{2k}) < p(q^{2k} + 1)$ and, since there are infinite prime numbers, the result follows.