Show that $1^k+2^k+3^k+ \ldots +n^k$ is divisible by $ 1+2+3+ \ldots +n$ [duplicate]
Solution 1:
Let $S_k=1^k+2^k+\cdots +n^k$. Since $$S_1=1+2+\cdots+n=\dfrac{n(n+1)}2$$ and $gcd(n,n+1)=1$, it suffices to show that $2S_k$ is divisible by $n$ and by $n+1$ separately.
Now $$2S_k =(1+n^k)+(2^k+(n-1)^k)+\cdots+(n^k+1)$$ and also $$2S_k=2n^k+(1+(n-1)^k)+(2^k+(n-2)^k)+\cdots+((n-1)^k+1).$$ And we are done (note that $k$ is odd).