# Prove that $\sum_{i=1}^{m-1} i^k$ is divisible by $m$

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

-

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

Use $k$ is odd.

-
Why is this true? –  timvermeulen Jun 22 '13 at 12:33
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
@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

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

-
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