Problem

Source: Romania TST 2015 Day 2 Problem 1

Tags: Sum, Divisibility, number theory, Romanian TST, GCD



Let $a$ be an integer and $n$ a positive integer . Show that the sum : $$\sum_{k=1}^{n} a^{(k,n)}$$ is divisible by $n$ , where $(x,y)$ is the greatest common divisor of the numbers $x$ and $y$ .