Write $\sum_{k=1}^n a^{(k,n)} = \sum_{d|n} \varphi(n/d)a^d$, where $\varphi$ is Euler's totient function ($\varphi(m)$ is the number of positive integers less than $m$ and prime to $m$), and notice that, if $n$ and $n'$ are coprime positive integers, then
$$\sum_{k=1}^{nn'} a^{(k,nn')} = \sum_{d|n} \varphi(n/d) \sum_{d'|n'} \varphi(n'/d')(a^d)^{d'}.$$
Consequently, it is sufficient to prove the assertion for $n = p^m$, where $p$ is a prime and $m$ is a non-negative integer. In this case,
$$\begin{aligned} \sum_{k=1}^{p^m} a^{(k, p^m)} &= \sum_{k=0}^{m} \varphi(p^{m-k}) a^{p^k} = \sum_{k=0}^{m-1} (p^{m-k} - p^{m-k-1}) a^{p^k} + a^{p^m} \\ &= p^m a + \sum_{k=1}^{m} p^{m-k} (a^{p^k} - a^{p^{k-1}}) \equiv 0 \pmod{p^m}, \end{aligned}$$
since $a^{p^k} \equiv a^{p^{k-1}} \pmod{p^k}$, $k = 1, \dots, m$, by Fermat's theorem.