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.

Prove that $\sum\limits_{i=1}^{m-1} i^k$ for odd numbers $m,k \in \mathbb{N}$ is divisible by $m$.

Because $m \mid m^k$, it is equivalent to the following:

Prove that $m \mid \sum\limits_{i=1}^{m} i^k$ for odd numbers $m,k \in \mathbb{N}$.

Say $m = 2t + 1$ with $t \in \mathbb{Z}$. For $k=1$, it is pretty obvious:

$$ \sum\limits_{i=1}^{2t+1} i = \frac{(2t+1)(2t+2)}{2} = (t+1)(2t+1) $$

which is an integer. For $k=3$, it is not that difficult either:

$$ \sum\limits_{i=1}^{2t+1} i^3 = \left( \sum\limits_{i=1}^{2t+1} i \right)^2 = \left( (t+1)(2t+1) \right)^2 $$

which again is an integer. However, I have used formulas for special sums, which do not apply to all odd numbers $k$. Can someone give a hint on how I can prove the statement for all odd numbers $k$?

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

Hint: $l^k + (m-l)^k = 0 \mod m$ for $l = 1,2,3 \cdots, m-1$

Use $k$ is odd.

share|improve this answer
    
Why is this true? –  timvermeulen Jun 22 '13 at 12:33
1  
Because the binomial terms always contain a factor of m. Write it out and you will see it. –  BlackAdder Jun 22 '13 at 12:57
1  
@timvermeulen- $(m-l)^k=\sum_{i=0}^{k} {m\choose i} (-1)^i m^{k-i}l^i$. If you expand, you'll realise the the only term in the expansion which is not divisible by m, is $-l^k$ (for an odd $k$). –  Ayush Khaitan Jun 22 '13 at 12:57
add comment

Unless $a^k\equiv b^k\equiv 0 {\pmod m}$, if $\displaystyle{a^k\equiv b^k \pmod m}$ where $k$ is an odd positive integer, then $a\equiv b \pmod m$.

Hence, none of $1^k,2^k,\dots (m-1)^k$ can have the same remainder when divided by $m$. This is because:

EDIT: Let $a^k\equiv (m-b)^k \pmod m$ for $a,b\in\{1,2,3,\dots (m-1)\}$, and $a\neq (m-b)$.

Then, by the above logic, $a\equiv (m-b) \pmod m$. Hence, $m-b-a\equiv 0 \pmod m$, which is obviously not possible, as $m-b-a\in (-m,m)$, and $a\neq (m-b)$

Clearly, none of them are $0(\mod m)$ either.

There are $m-1$ possible remainders then: $1,2,3\dots (m-1)$. The expression we get is $$\sum_{i=1}^{m-1}i^k=1+2+3+\dots m-1$$

This is equal to $$\frac{m(m-1)}{2}$$

As $m$ is odd, $m-1$ is divisible by $2$. Hence, we get a number that is a product of $m$.

share|improve this answer
2  
Your very first line is false unless you add further conditions: $$0^3=2^3\pmod 8\;,\;\;but\;\;0\neq 2\pmod 8\;;\;\;0^3=6^3\pmod{12}\;,\;\;but\;\;0\neq 6\pmod{12}\ldots$$ –  DonAntonio Jun 22 '13 at 12:59
    
Should the condition be both $a^k$ and $b^k$ are not divisible by $m$? –  Ayush Khaitan Jun 22 '13 at 13:00
    
Yes I think this condition is right. If $a\equiv l_{1} \pmod m$ and $b\equiv l_{2} \pmod m$, where $l_{1},l_{2}\not\equiv 0$, and $a^k\equiv b^k \pmod m$, then $l_{1}=l_{2}$. This is clear on writing it as $(mc+l_{1})^k\equiv (md+l_{2})^k \pmod m$, where $k$ is odd, and expanding binomially. –  Ayush Khaitan Jun 22 '13 at 13:07
    
Well @Ayush, I also think $\,m\,$ is assumed odd from the start... –  DonAntonio Jun 22 '13 at 13:08
    
@DonAntonio- yes. I have assumed the same in my answer. Where am I contradicting this fact? I have also stated that $m-1$ is divisible by $2$ because $m$ is odd. –  Ayush Khaitan Jun 22 '13 at 13:12
add comment

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.