Let $r$ be a primitive root modulo $p$. It's quite well-known that $\{1,2,3,\ldots,p-1\}$ are congruent to $\{r,r^2,\ldots,r^{p-1}\}$ modulo $p$ in some order. So the given sum is nothing but \begin{align*} 1^n+2^n+3^n+\ldots+(p-1)^n &\equiv \underbrace{r^n+r^{2n}+r^{3n}+\ldots+r^{(p-1)n}}_{\text{In some order}} \pmod{p}\\ &\equiv r^n \left(\frac{r^{(p-1)n}-1}{r^n-1}\right) \pmod{p} \\ &\equiv 0 \pmod{p} \\ \end{align*}which shows what we desired $\square$