XVII OBM

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\ne l$ (indeed, if $d$ is such $\gcd$ and $k<l$,

$$q^{2k}\equiv -1(\mathrm{mod}d)⟹q^{2l}\equiv 1(\mathrm{mod}d)⟺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.