Prove that $a$ divides $1^{a^{n}} + 2^{a^{n}} + … + (a-1)^{a^{n}}$?

Let $a > 2$ be an odd number and let $n$ be a positive integer. Prove that $a$ divides $1^{a^{n}} + 2^{a^{n}} + ... + (a-1)^{a^{n}}$ ? (ref. Titu Andreescu, Number theory, page no. 5).

I am not getting any clue as to how to approach the solution.

• Hint: $a^n$ is odd. You don't need more for the exponents. – Daniel Fischer Nov 12 '15 at 15:16

First note that whenever $m$ is odd, $x^m+y^m$ is divisible by $x+y$. More specially, $k^m + (a-k)^m$ is divisible by $a$, whenever $m$ is odd.
We now have $$\sum_{k=1}^{a-1} k^{a^n} = \sum_{k=1}^{(a-1)/2} \left(k^{a^n}+(a-k)^{a^n}\right)$$ and since $a^n$ is odd, we have that $k^{a^n}+(a-k)^{a^n}$ is divisible by $a$, which in turn means that every term is divisible by $a$.