Problem: Let $p$ be a prime number.
Prove that there exists a prime number $q$ such that for every integer $n$,
the number $n^p-p$ is not divisible by $q$.

\end{enumerate}

Solution: By orders, we must have $q=pk+1$ for this to be possible
(since if $q \not \equiv 1 \pmod p$, then $n^p$ can be any residue modulo $q$).
Since $p \equiv n^p \pmod q \implies p^k \equiv 1 \pmod q$,
it suffices to prevent the latter situation from happening.

So we need a prime $q \equiv 1 \pmod p$ such that $p^k \not\equiv 1 \pmod q$.
To do this, we first recall the following lemma.
\begin{lemma*}
  Let $\Phi_p(X) = 1 + X + X^2 + \dots + X^{p-1}$.
  For any integer $a$, if $q$ is a prime divisor of $\Phi_p(a)$ other than $p$,
  then $a \pmod q$ has order $p$. (In particular, $q \equiv 1 \pmod p$.)
\end{lemma*}
\begin{proof}
  We have $a^p-1 \equiv 0 \pmod q$, so either the order is $1$ or $p$.
  If it is $1$, then $a \equiv 1 \pmod q$, so $q \mid \Phi_p(1) = p$, hence $q = p$.
\end{proof}

% Wishfully we hope the order of $p$ is $p$ and $k \nmid p$.
Now the idea is to extract a prime factor $q$
from the cyclotomic polynomial
\[ \Phi_p(p) = \frac{p^p-1}{p-1} \equiv 1+p \pmod{p^2} \]
such that $q \not\equiv 1 \pmod{p^2}$;
hence $k \not\equiv 0 \pmod p$,
and as $p \pmod q$ has order $p$ we have $p^k \not\equiv 1 \pmod q$.