# Prove that $1^k + 2^k + \cdots + n^k$ is divisible by $1 + 2 + \cdots + n$

This is a problem from Terence Tao's Solving mathematical problems, a personal perspective. The problem is:

Let $$k,n\in\mathbb{N}$$ with $$k$$ odd. Prove that the sum $$1^k+2^k+\cdots+n^k$$ is divisible by $$1+2+\cdots+n$$.

Here is the text's solution. However, I thought that the second modulus congruence that goes on like:

$$1^k+2^k+3^k+\cdots+(m-1)^k+0^k +1^k+\cdots+(m-1)^k + 0\pmod m$$."

Could be simplified as

$$1^k+2^k+3^k+\cdots+(m-1)^k+0^k+(-(m-1))^k+\cdots+(-1)^k+0 \pmod m$$ Now since $$k$$ is odd, $$(-1)^k$$ has to be $$-1$$. Similarly, $$(-(m-1))^k$$ has to be $$-(m-1)^k$$. Therefore, the first $$m-1$$ terms cancel with the last $$m-1$$ terms.

I'll show a simpler method than modular arithmetic.

Denote the first sequence $$S_k = 1^k + 2^k + \cdots + n^k$$.

Now the key step lies in seeing that $$1 + 2 + \cdots + n = \dfrac{n(n + 1)}2$$ (can you prove why)?

So we want to prove that $$(n^2 + n) \mid 2S_k$$, so we only need to show that $$n \mid 2S_k$$ and $$(n + 1) \mid 2S_k$$.

So rewrite $$2S_k = (1 + n^k) + (2^k + (n - 1)^k) + \cdots + (n^k + 1)$$ which is divisible by $$n+1$$ and $$2S_k=2n^k+(1+(n-1)^k)+(2^k+(n-2)^k)+\cdots+((n-1)^k+1)$$ which is divisible by $$n$$.

• Similar question here: math.stackexchange.com/questions/4629024/… Nice observation, thanks! Commented Feb 8, 2023 at 20:40
• Very nice and clever! +1
– Mike
Commented Feb 15, 2023 at 21:23