Let $p$ be a prime number. Determine the remainder of the Euclidean division of $1^{k}+\cdots+(p-1)^{k}$ for any integer $k \geq 0$ by $p$ (without primitive root).
Let's recall that $X^{p}-X=\prod_{k=0}^{p-1}(X-k)$ in $\mathbb{Z} / p \mathbb{Z}$.

We use Newton's relations applied to the elements $0, \ldots, p-1$ in $\mathbb{Z} / p \mathbb{Z}$. Let $\sigma_{k}$ for $k \in \mathbb{N}$ denote the elementary symmetric polynomials (with $\sigma_{k}=0$ if $k \geq n$), and $S_{k}$ the sums of the $k$-th powers for $k \in \mathbb{N}$. For all $k \geq 1$, we have:

$$
\sum_{r=0}^{k-1}(-1)^{r} \sigma_{r} S_{k-r}+(-1)^{k} k \sigma_{k}=0
$$

We can easily compute the $\sigma_{k}$ from the polynomial $X^{p}-X: \sigma_{0}=0, \sigma_{i}=0$ for $i \geq 1$, except if $i=n-1$: in this case $(-1)^{p-1} \sigma_{p-1}=-1$, so $\sigma_{p-1}=-1$ (this is true if $p$ is odd, and it is easily verified if $p=2$). In particular, Newton's relations become $S_{k}+(-1)^{p-1} \sigma_{p-1} S_{k-(p-1)}$ if $k \geq p, S_{k}=0$ if $0<p-1, S_{k}=0$ if $0<k<p-1$, and $S_{p-1}=-1$. By immediate induction, we obtain that the remainder of the Euclidean division of $1^{k}+\cdots+(p-1)^{k}$ is $p-1$ if $k$ is divisible by $p-1,0$ otherwise (for $k=0$, the sum is $S_{0}-1$).