# $1^n$ + $2^n$ + · · · + $n^n$ is divisible by $n^2$ where $n$ is an odd positive integer

Let $n$ be an odd positive integer. Show that the sum $1^n$ + $2^n$ + · · · + $n^n$ is divisible by $n^2$.

I tried induction on $n$ and thought of manipulating the terms by separating for example $3^{2n+3}$ into $3^{2n+1}\cdot 3^2$... then thought the sum of the squares of integers would play in to showing the inductive proof step for $n=2k+3$.

Using the binomial theorem, note that $k^n+(n-k)^n$ is congruent to $k^n+(-1)^nk^n$ modulo $n^2$, and since $n$ is odd, this is zero. Thus, pair off all terms, except the last one which is divisible by $n^2$.
• @RandinMichaelDivelbiss $1^n \equiv -(n-1)^n \pmod {n^2}$, $2^n \equiv -(n-2)^n \pmod {n^2}$, and so on, because $n$ is odd, and because $(n-k)^n = (\text{terms having n with power }\ge 2) + (-1)^{n-1}n^2k^{n-1} + (-1)^nk^n$, due to which only the last term remains. So, all such pairs cancel out and only $n^n \pmod {n^2}$ is left, which is $0$. – GoodDeeds Jun 19 '18 at 5:10