Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.