MathNet 2015-part-04 — 191 problems (EN–VI) Question 97

Given an integer $a$ and a positive integer $n$, show that the sum $\sum_{k=1}^{n} a^{(k,n)}$ is divisible by $n$, where $(x, y)$ denotes the greatest common divisor of the integers $x$ and $y$.