Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
7  
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
add comment

1 Answer

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|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
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 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
show 3 more comments

Your Answer

 
discard

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.