For which $n$ does $n\mid 1^n+2^n+\cdots+n^n$? Find all the natural numbers $n$ such that
$$n\mid 1^n+2^n+\cdots+n^n.$$
We know through Faulhaber's formula, that 
$$\sum_{k=1}^{n}k^n=\frac1{n+1}\sum_{k=0}^n\binom{n+1}{k}B_k n^{n+1-k},$$
where $B_k$ is a Bernoulli number. I checked few dozen values of $n$ and it seems that only odd numbers are solutions. Any ideas on how to proceed from here?

Hint: To show it works for odd $n$,note you can ignore the term $n^n$ and then if you take the first and last terms mod $n$ you get $1^n$ and $(-1)^n$ which cancel (because $n$ is odd) and similarly the second and second to last terms are $2^n$ and $(-2)^n$ which cancel, and so forth (all because $n$ is odd).
Not sure how to prove it fails for $n$ even.
