1

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

Fly by Night
  • 32,272
user64370
  • 381

1 Answers1

1

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

lab bhattacharjee
  • 274,582
  • 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 01 '13 at 18:25
  • @ThomasAndrews, even if for all integer $n$ and $0\le r\le n?$ – lab bhattacharjee Mar 01 '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 01 '13 at 18:41
  • 1
    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 01 '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 02 '13 at 03:27
  • No, you've proved that, when $k$ is even, $n$ can't divide $r^k+(n-r)^k$, but you have not proved that, when $k$ is even, $n$ can't divide $\sum_{r=1}^k r^k +(n-r)^k$. That second statement does not follow from the first statement. For example, it might be possible that $r^k+(n-r)^k\equiv 1\pmod n$. You haven't proven that can't happen. So you haven't proven anything in the case $k$ even. (As I say, it is easy to prove when $k$ even just by looking at $n=2$.) – Thomas Andrews Mar 02 '13 at 04:11
  • For example, $1^2+2^2+3^2+4^2=30$ is divisible by $1+2+3+4=10$. So it is not true for any $n$. Indeed, when $k=2$, it doesn't work for any $n\equiv 1\pmod 3$. – Thomas Andrews Mar 02 '13 at 04:16
  • (That was in ref to your original proof, which was correct for $k$ odd, but got confused when $k$ even. The edited version, which i did not notice, removes that error.) – Thomas Andrews Mar 02 '13 at 04:25