Show that $1^k+2^k+3^k+ \ldots +n^k$ is divisible by $ 1+2+3+ \ldots +n$ If $k$ is an odd positive integer, prove that for any integer $ n\geq 1$, $(1^k+2^k+3^k+ \ldots +n^k)$ is divisible by $ (1+2+3+ \ldots +n)$.
I didn't get how it is connected( or different) than this: suppose that $n$ is natural number and even, show that $ n∤1^n+2^n+3^n+…(n−1)^n$
I tried for small numbers $n=3,4$ then use induction on $k$  but how to show for any natural $n$? does the answer in the link provides an insight to the solution.
Hints would suffice. Thanks

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).
