Proving $\sum_{k=1}^m{k^n}$ is divisible by $\sum_{k=1}^m{k}$ for $ n=2013$ I got an interesting new question, it's about number theory and algebra precalculus. Here is the question:

a positive integer $n$ is called valid if $1^n+2^n+3^n+\dots+m^n$ is divisible by $1+2+3+\dots+m$ for every positive integer $m$.
  
  
*
  
*Prove that 2013 is valid
  
*Prove that there are infinite positive integers which are not valid
  

Every little hint, contribution and recommendation would be very helpful. Sorry for my bad english. Thanks before.
 A: If $n$ is odd, then modulo $m+1$ we have $2(1^n + 2^n + \ldots + m^n) = (1^n+m^n) + (2^n+(m-1)^n) + \ldots + (m^n+1^n) \\ \equiv (1^n-1^n) + (2^n-2^n) + \ldots + (m^n-m^n) = 0 \pmod {m+1}$.
Also, since $m^n \equiv 0 \pmod m$, $2(1^n + 2^n + \ldots + m^n) \equiv 2(1^n + 2^n + \ldots + (m-1)^n) \equiv 0 \pmod m$
Since $m$ and $m+1$ are coprime, this shows that $2(1^n + \ldots + m^n)$ is a multiple of $m(m+1)$, and since $m(m+1)$ is even, $1^n + \ldots + m^n$ is a multiple of $m(m+1)/2 = 1+2+\ldots+m$.
If $n$ is even then $1+2^n \equiv 2 \pmod 3$, which is not a multiple of $1+2 = 3$
A: All odd $n$ are valid. In fact, for all odd $n$, $1^n + 2^n + 3^n + \dots + m^n$ is actually a polynomial in $1 + 2 + 3 + \dots + m = m(m+1)/2$. These polynomials are known as Faulhaber polynomials (see https://en.wikipedia.org/wiki/Faulhaber%27s_formula#Faulhaber_polynomials). You can find a proof of this fact in the AMM article "Sums of Powers of Integers" (modifying the proof slightly also shows the divisibility relation you want, but there are also easier ways to do this; see mercio's solution).
To answer your second question, all even $n$ are not valid; this can be easily seen by noticing that $2^n + 1$ is not divisible by $3$ if $n$ is even.
