Prove that if $n>1$ is odd, then $1^n+2^n+3^n+\ldots+(n-1)^n$ is divisible by $n$

Question

Prove that if $n>1$ is odd, then $1^n+2^n+3^n+\ldots+(n-1)^n$ is divisible by $n$.

I'm pretty sure I need to prove this using induction but I am unsure as to how to go about it.

Answer 1

Hint: If $n$ is odd, $$ 1^n+(n-1)^n \equiv 1^n+(-1)^n \equiv 0\pmod{n}, $$ $$ 2^n+(n-2)^n \equiv 2^n+(-2)^n \equiv 0\pmod{n} $$ and so on.

Answer 2

Just prove that for odd $n$, $a^n + b^n$ is divisible by $a+b$. This can be done easily by induction or binomial theorem.

Then the result follows as we can group terms equidistant from both ends: $$[1^n + (n-1)^n] +[ 2^n + (n-2)^n] \dots$$

where each term in $[\dots]$ is divisible by $n$.

Answer 3

Another method to prove that $a+b\mid a^n+b^n$ when $a,b,n\in\mathbb Z$, $n\ge 1$, $n$ is odd is:

let $c\in\mathbb Z$.

$$a^n-c^n=(a-c)\left(a^{n-1}+a^{n-2}c+\cdots+c^{n-1}\right)$$

Let $c=-b$. Use that $n$ is odd. $$a^n+b^n=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots+b^{n-1}\right)$$

Therefore $n\mid 1^n+(n-1)^n$, $n\mid 2^n+(n-2)^n$, $\ldots$, $n\mid \left(\frac{n-1}{2}\right)^n+\left(\frac{n+1}{2}\right)^n$.