# Describe the set of all good numbers

A natural number $k$ is considered good, if for each $n$ the number $1^k+2^k+\cdots+n^k$ is divisible by $1+2 +\cdots+n$. Describe the set of all good numbers (with proof).

-
What have you tried? –  Tobias Kildetoft Mar 1 '13 at 18:10
The problem seems to be from here, and the answer is given here. –  Ilmari Karonen Mar 1 '13 at 19:14
@IlmariKaronen - thanks a lot! –  user64370 Mar 1 '13 at 22:10

We know, $1+2+\cdots+(n-1)+n=\frac{n(n+1)}2$

As Thomas has pointed out $3\not\mid(1+2^k)$ for even $k,$ so $k$ can not be even.

Now, $r^k+(n-r)^k\equiv r^k\{1+(-1)^k\} \pmod n$

So, $r^k+(n-r)^k\equiv r^k(1-1)\equiv0\pmod n$ for all $r\in[0,n]$ if $k$ is odd

So, $n\mid\{r^k+(n-r)^k\}$ if and only if $k$ is odd

Putting $r=0,1,\cdots,n$ and summing them we get $n\mid 2\sum_{1\le r\le n}r^k$

Again, $r^k+(n+1-r)^k\equiv r^k\{1+(-1)^k\} \pmod {n+1}$

So, $(n+1)\mid\{r^k+(n-r)^k\}$ if and only if $k$ is odd

Putting $r=0,1,\cdots,n+1$ and summing them we get $(n+1)\mid 2\sum_{1\le r\le n+1}r^k\implies (n+1)\mid 2\sum_{1\le r\le n}r^k$

So, $lcm(n,n+1)\mid 2\sum_{1\le r\le n}r^k$ if and only if $k$ is odd

$\implies \frac{n(n+1)}2\mid \sum_{1\le r\le n}r^k$ if and only if $k$ is odd as gcd$(n,n+1)=$gcd$(n,1)=1\implies$lcm$(n,n+1)=n(n+1)$

-
Just because $n\not |r^k+(n-r)^k$, we can't conclude that $n\not|\sum (r^k+(n-r)^k$ –  Thomas Andrews Mar 1 '13 at 18:25
@ThomasAndrews, even if for all integer $n$ and $0\le r\le n?$ –  lab bhattacharjee Mar 1 '13 at 18:27
Well, it might just be easier to show that if $k$ is even, then $1+2^k$ is not divisible by $3$ :) –  Thomas Andrews Mar 1 '13 at 18:41
But I don't see how your attempt proves it. I think your result is right - the odd numbers are the only ones that satisfy this - but your proof essentially is for fixed $n$, and doesn't seem to use that it is true for all $n$ to reach a contradiction. –  Thomas Andrews Mar 1 '13 at 18:44
@ThomasAndrews, I'm not sure what you meant by fixed $n.$ The conclusion I've reached, will hold true for any positive integral value of $n,$ right? Also, included your logic to cancel out the even values of $k$ –  lab bhattacharjee Mar 2 '13 at 3:27