Case 1 If $p|n^2-1$ then $n^2-1\geq p\Leftrightarrow n\geq \sqrt{p+1}>\sqrt{p}>\sqrt{p}-1$ Case 2 If $(p,n^2-1)=1$ then $p|(n^2+n+1)(n^2-n+1)$ so $p|(n^2+n+1) \,\,\,\,or\,\,\,\,(n^2-n+1)$ In each case we have that $n^2+n+1\geq p$ so it suffice to show that $(n+1)^2>n^2+n+1$ which is true .