Shortlist JBMO, 2007

Solution:

Since $n \mid p-1$, then $p = 1 + n a$, where $a \geq 1$ is an integer. From the condition $p \mid n^{6}-1$, it follows that $p \mid n-1$, $p \mid n+1$, $p \mid n^{2}+n+1$ or $p \mid n^{2}-n+1$.

- Let $p \mid n-1$. Then $n \geq p+1 > n$ which is impossible.

- Let $p \mid n+1$. Then $n+1 \geq p = 1 + n a$ which is possible only when $a=1$ and $p = n+1$, i.e. $p-n = 1 = 1^{2}$.

- Let $p \mid n^{2}+n+1$, i.e. $n^{2}+n+1 = p b$, where $b \geq 1$ is an integer.

The equality $p = 1 + n a$ implies $n \mid b-1$, from where $b = 1 + n c$, $c \geq 0$ is an integer. We have
$$n^{2}+n+1 = p b = (1 + n a)(1 + n c) = 1 + (a + c) n + a c n^{2} \text{ or } n+1 = a c n + a + c$$
If $a c \geq 1$ then $a + c \geq 2$, which is impossible. If $a c = 0$ then $c = 0$ and $a = n+1$. Thus we obtain $p = n^{2} + n + 1$ from where $p+n = n^{2} + 2 n + 1 = (n+1)^{2}$.

- Let $p \mid n^{2}-n+1$, i.e. $n^{2}-n+1 = p b$ and analogously $b = 1 + n c$. So
$$n^{2}-n+1 = p b = (1 + n a)(1 + n c) = 1 + (a + c) n + a c n^{2} \text{ or } n-1 = a c n + a + c$$
Similarly, we have $c = 0$, $a = n-1$ and $p = n^{2} - n + 1$ from where $p-n = n^{2} - 2 n + 1 = (n-1)^{2}$.