MathNet 2014 Question 91

Let $p$ be a prime number and $n \geq 2$ a positive integer, such that $p \mid (n^{6}-1)$. Prove that $n \gt \sqrt{p} - 1$.