Prove that the statement $(1+2+3+ \cdots + n) \mid (1^m+2^m+3^m+ \cdots +n^m)$ is true for all odd numbers $m$

Question

My first idea to this problem is proved by induction (obviously by induction). So I tried to solve it by Induction, but after 30-45 minutes it just didn't give me enough information to prove it. Also I tried both weak and strong induction and get nothing.

Answer 1

Do you know modular arithmetic? This problem is much clearer to understand in that setting (it becomes obvious why the exponent $m$ is being taken as odd), while it seems totally opaque and strange as a plain induction problem.

Update: since you know modular arithmetic, then in order to show $1^m + 2^m + \cdots + n^m \equiv 0 \bmod n(n+1)/2$, take cases if $n$ is even or odd.

Suppose $n$ is even, so $n(n+1)/2 = (n/2)(n+1)$ where $n/2$ and $n+1$ are relatively prime. Mod $n$, we have $$ 1^m + 2^m + \cdots + n^m \equiv 1^m + 2^m + \cdots + (n-1)^m \bmod n $$ and $j^m + (n-j)^m \equiv j^m + (-j)^m \equiv j^m - j^m \equiv 0 \bmod n$ because $m$ is odd. Thus the sums $1^m + (n-1)^m$, $2^m + (n-2)^m$, and so on all vanish mod $n$. The only term that survives is the solitary term $(n/2)^m$, so $$ 1^m + 2^m + \cdots + n^m \equiv (n/2)^m \bmod n. $$ Now reduce modulo $n/2$ to kill off the right side, giving us $1^m + 2^m + \cdots + n^m \equiv 0 \bmod n/2$ when $n$ is even.

Next, show $1^m + 2^m + \cdots + n^m \equiv 0 \bmod n+1$ because $j^m + (n+1-j)^m \equiv 0 \bmod n+1$, and these pairings account for everything on the left side since there is no middle term this time: $n+1$ is odd when $n$ is even.

Thus when $n$ is even, $1^m + 2^m + \cdots + n^m$ is divisible by $n/2$ and by $n+1$, which are relatively prime, so that sum is divisble by $n(n+1)/2$.

The case of odd $n$ is similar and left to you.