# Prove that $1^n+2^n+…+(n-1)^n$ is divisible by $n$ if $n$ is odd?

I've tried this with a few examples, but how would I show that it's true for EVERY odd number $$n$$? And why wouldn't it work for even number $$n$$?

• It wouldn't work for even number $n$ because $1^2$ is not divisible by $2$, so $n=2$ is invalid. That being said, the problem doesn't say that it doesn't work for (at least some) even numbers. It just asks you to show that it does work for odd numbers. – Arthur Apr 19 at 23:16
• For even $n$ see OEIS A182398 – Henry Apr 19 at 23:39
• Essentially a dupe of this and likely many others. See there for links to generalizations. – Bill Dubuque Apr 19 at 23:50

## 3 Answers

Suppose $$n$$ is an odd number. Note that the sequence $$1,2,3,...,n-1$$ can be written like this:

$$1,2,...,\frac{n-1}{2},n-\frac{n-1}{2},...,n-2,n-1$$.

For each $$k\in\{1,2,...,\frac{n-1}{2}\}$$ we obviously have $$n-k\equiv -k$$(mod $$n$$). Since $$n$$ is odd $$(-k)^n=-k^n$$ and hence $$(n-k)^n\equiv -k^n$$(mod $$n$$). And from here we get:

$$1^n+2^n+...+(n-1)^n\equiv 1^n+2^n+...+(\frac{n-1}{2})^n-(\frac{n-1}{2})^n-...-2^n-1^n\equiv 0$$(mod $$n$$).

So the sum is divisible by $$n$$ just as we wanted.

As for even values take $$n=2$$ as a counterexample.

Hint:

• For odd $$n$$, can you show $$k^n+(n-k)^n$$ is divisible by $$n$$? (Try the binomial expansion)

• Then add these up for $$k \in \{1,2,\ldots,\frac{n-1}{2}\}$$

Firstly, $$k\equiv k-n \mod n$$.

For odd $$n>1$$, $$A:=\sum^{n-1}_{k=1}k^n\equiv \sum^n_{k=1}k^n\equiv\sum^{n}_{k=1}(k-n)^n=-\sum^n_{k=1}(n-k)^n=-\sum^n_{k=1}k^n\equiv-\sum^{n-1}_{k=1}k^n =-A\mod n$$

$$A\equiv -A \mod n\implies 2A\equiv 0\mod n$$.

Hence, either $$2\equiv 0\mod n$$ (impossible) or $$A\equiv 0\mod n$$, which is the desired conclusion.