GCD of sums of n consecutive n-th powers It is an easy exercise to show that all sums of 3 consecutive 3rd powers are divisible by 9. (e.g. by induction or modular arithmetic)
Experimentation in Mathematica suggests that more generally, for all odd $n\in\mathbb{N}$ the numbers
$
a^n+(a+1)^n+\dots+(a+n-1)^n,\qquad a\in\mathbb{N}
$
are divisible by $n^2$. Actually, the stronger statement that $n^2$ is the GCD seems to be true.
Any ideas on how to approach this?
 A: Let $f(a, n) = a^n + (a+1)^n + \cdots + (a+n-1)^n$.  Let $n = 2m+1$.  Then it suffices to show:
First, a base case, $f(-m, 2m+1) = 0$.  This is simple: the sum is 
$$(-m)^{2m+1} + (-(m-1)^{2m+1})) + \cdots + (m-1)^{2m+1} + m^{2m+1}$$
and terms cancel in pairs except for the middle term, which is $0^{2m+1} = 0$.
Second, an inductive step.  It suffices to show that $f(a, n)$ and $f(a+1, n)$ differ by a multiple of $n^2$ and are therefore congruent mod $n^2$.  But these two sums differ by adding and removing one term -- you have
$$f(a+1, n) - f(a, n) = (a + n)^n - a^n$$
and you want to show that this is divisible by $n^2$.  But this is just
$$ \left( \sum_{k=0}^n {n \choose k} a^{n-k} n^k \right) - a^n $$
or, noting that $a^n$ is the $k = 0$ term of the sum,
$$  \sum_{k=1}^n {n \choose k} a^{n-k} n^k  $$
To show that that sum is divisible by $n^2$, you need to show that each term is divisible by $n^2$.  Obviously the terms with $k \ge 2$ are.  The $k = 1$ term is ${n \choose 1} a^{n-1} n^1 = n^2 a^{n-1}$ so it's divisible by $n^2$ as well. 
