Tenemos $p^p-1 = (p-1)(1+p+\cdots+p^{p-1})$. Si $q$ primo divide a ambos factores, $q\mid p-1$ y $0 \equiv 1+p+\cdots+p^{p-1} \equiv p \, {(\text{mód }q)}$, luego $q\mid p$, $q\mid 1$ y $q=1$, absurdo, por lo que son coprimos. Sea $q_1\ldots q_r$ una descomposición en primos de $\frac{p^p-1}{p-1}$. Si $p^2 \mid q_i - 1$ para todo $i=1,\ldots,r$ entonces $p^2 \mid q_1\ldots q_r - 1 = \frac{p^p-1}{p-1} - 1$ y $p^2 \mid p^p-1-(p-1)=p^p-p$, por lo que $p^2 \mid p$, absurdo. Entonces hay un primo $q$ que divide a $\frac{p^p-1}{p-1}$ tal que $p^2 \nmid q-1$. Como probamos que $\frac{p^p-1}{p-1}$ y $p-1$ son coprimos, $q\nmid p-1$. Además, $q\mid p^p -1$, luego $p$ y $q$ son coprimos y $p$ es el orden de $p$ módulo $q$; luego, por el pequeño teorema de Fermat (dice que $q\mid p^{q-1}-1$), $p\mid q-1$. (El orden de $a$ módulo $b$, dados dos enteros positivos coprimos $a,b$, es el menor entero positivo $r$ tal que $b\mid a^r-1$. Siempre existe y cumple que si $b\mid a^s-1$ entonces $r\mid s$.)
Veamos que $q$ cumple lo que pide el enunciado. Sea $n$ entero. Si $q\mid n^p-p$, $q$ y $n$ son coprimos (porque $q$ y $p$ son coprimos), y $n^p \equiv p\, (\text{mód }q)$. Como $p\mid q-1$, tenemos $n^{p\frac{q-1}p} = n^{q-1} \equiv 1\,(\text{mód }q)$, luego $p^{\frac{q-1}p}\equiv 1\,(\text{mód }q)$ y como $p$ es el orden de $p$ módulo $q$, tenemos $p\mid \frac{q-1}p$, es decir, $p^2\mid q-1$. Pero por cómo elegimos $q$ teníamos $p^2 \nmid q-1$, absurdo. Entonces para todo entero $n$ tenemos $q\nmid n^p-p$, como pide el enunciado.
