The most elementary proof of divisibility of sum of powers I am wondering how one can prove that for an arbitrary odd natural number $n$ and an arbitrary natural number $a$ the power-sum $S_{(a,n)}=1^n+2^n+\ldots +a^n $ is divisible by $S_{(a,1)}=1+2+\ldots + a$ in the most elementary way (possible) which comes to your mind. By an elementary way I mean the way which even middle school student could follow.
I traditionally tried to compute $S_{(a,n)}$ using the expansion of $(x-1)^{n+1}=\sum_{k=0}^{n+1}(-1)^k\binom{n+1}{k}x^{n+1-k}$.
I substituted $x=1,2,3,\ldots , a$ and then summed up results. After telescoping and cancelations I received $a^{n+1}=\sum_{k=1}^{n+1}(-1)^{k+1}\binom{n+1}{k}S_{(a,n+1-k)}$, from which we can express $S_{(a,n)}$.
Nevertheless this approach seems to me tough and not so easy to follow for a middle school student; A loads of technical re-writing and quite long symbolic computations needed to go through.
My question: I am missing something very evident and elegant which gives the desired divisibility without tears?

Note that $r^n+(P-r)^n$ is divisible by $P$ by Binomial expansion and cancelling of the only terms without factors of $P$ (as $n$ is odd). If $a$ is odd, then all the terms in $S_{(a,n)}$ pair up in this way, with $P=a$, except for $a^n$, which is certainly a multiple of $a$, so $S_{(a,n)}$ is a multiple of $a$. If $a$ is even, then all the terms in $S_{(a,n)}$ pair up in this way, except for $a^n$ and $\Big(\dfrac{a}{2}\Big)^n$, so so $S_{(a,n)}$ is a multiple of $\dfrac{a}{2}$. We can make exactly the same argument with $P=a+1$, except that, if $a$ is odd, we find $S_{(a,n)}$ is a multiple of $\dfrac{a+1}{2}$ and if $a$ is even, $S_{(a,n)}$ is a multiple of $a+1$. Hence $S_{(a,n)}$ is always a multiple of $\dfrac{a(a+1)}{2}=S_{(a,1)}$.
Illustrative examples.
$1^n+2^n+3^n+4^n+5^n=(1^n+4^n)+(2^n+3^n) + 5^n$, so divisible by 5; also $1^n+2^n+3^n+4^n+5^n=(1^n+5^n)+(2^n+4^n) + 3^n$, so divisible by 3.
$1^n+2^n+3^n+4^n+5^n+6^n=(1^n+5^n)+(2^n+4^n) + 3^n +6^n$, so divisible by 3; also $1^n+2^n+3^n+4^n+5^n+6^n=(1^n+6^n)+(2^n+5^n) + (3^n+4^n)$, so divisible by 7.
