Let $k\in\mathbb{N}, 2<p\in\mathbb{P}, p^{\alpha}\mid\mid n,\alpha\ge1$. Then prove that $$1^k+2^k+\ldots+n^k\equiv\begin{cases}\hfill 0\pmod{p^{\alpha}},& p-1\nmid k\\-\frac{n}{p}\pmod{p^{\alpha}},& p-1\mid k\end{cases}$$
Firstly, I proved for $n=p$. If $p-1\mid k$, then it can easily proved by Fermat's little theorem. Let $p-1\nmid k$. Since $p$ is a prime, it has a primitive root $g$ and it satisfies $\{1,g,g^2,\ldots,g^{p-2}\}=\{1,2,3,\ldots,p-1\}$. So it's sufficient to prove that $1+g^k+g^{2k}+\ldots+g^{(p-2)k}\equiv 0\pmod p\iff p\mid\frac{g^{(p-1)k}-1}{g^k-1}\iff p\cdot (g^k-1)\mid g^{(p-1)k}-1$. Since $(p, g^k-1)\neq1\iff p-1\nmid k$ and $p\mid g^{(p-1)k}-1,g^k-1\mid g^{(p-1)k}-1$, it's true.
And I can't continue that for $n=p^{\alpha}$ (for $p-1\nmid k$, it's similar to $n=p$. But I can't prove for $p-1\mid k$), $n=p^{\alpha}\cdot n_1$, where $n_1>1, (n_1,p)=1$ and so on. Can anyone help me?
Best Answer
It's not difficult to check that it's enough to show it for $n=p^{\alpha}$.
We'll show it by induction over $\alpha$.
If $\alpha=1$ then it works. Assume the result holds for $\alpha-1$.
Then, mod $p^{\alpha}$, $\sum_{m=0}^{p^{\alpha}-1}{m^k} = \sum_{m=0}^{p^{\alpha-1}-1}{\sum_{l=0}^{p-1}{(m+p^{\alpha-1}l)^k}} = \sum_{m=0}^{p^{\alpha-1}-1}{\sum_{l=0}^{p-1}{m^k+kp^{\alpha-1}l}}=p\sum_{k=0}^{p^{\alpha-1}-1}{m^k}+kp^{\alpha-1}\sum_{l=0}^{p-1}{l} = p\sum_{k=0}^{p^{\alpha-1}-1}{m^k} = -p \cdot p^{\alpha-1}/p = -p^{\alpha}/p$.