$(3)$ Prove that if $k$ is odd, the sum $1^k+2^k+3^k+$cdots$+n^k$ will always

be divisible by the sum $1+2+3+$cdots$+n,$ regardless of $n.$

Hint: What is the formula for the sum $1+2+$cdots$+n?$ Consider

the cases $n$ even and odd separately. Divide and Conquer.