Very nice problem here is my solution: Lemma1: $\sum_{1\le k\le n}a^{(n,k)}=\sum_{d\mid n}\phi (d)a^{\frac{n}{d}}$. Prove: just observe that the number of positive integers $k$ such that $(k,n)=d$ is $\phi (\frac{n}{d})$ because $(\frac{n}{d},\frac{k}{d})=1$. So the lemma proved. Lemma2: for a prime number $p$ and for natural numbers $k,a$ such that $(a,p)=1$ we have $a^{p^{k}}\equiv a^{p^{k-1}}\pmod{p^k}$. Prove: it's just Euler's formula note that $a^{\phi (p^k)}\equiv 1\pmod{p^k}\longrightarrow a^{p^{k}}\equiv a^{p^{k-1}}\pmod{p^k}$. We first prove the claim for power of primes let $n=p^s$ such that $p$ is a prime number. Note that from the lemma1: $\sum_{1\le k\le p^s}a^{(p^s,k)}=\sum_{d\mid p^s}\phi (d)a^{\frac{p^s}{d}}=a^{p^s}+(p-1)a^{p^{s-1}}+(p^2-p)a^{p^{s-2}}+\cdots +(p^s-p^{s-1})a$(1).we prove this by induction on $s$. From the lemma2 $a^{p^s}+(p-1)a^{p^{s-1}}\equiv a^{p^{s-1}}+(p-1)a^{p^{s-1}}=p a^{p^{s-1}}$ now substituting this in (1) we an dividing $p$ the sum we get that: $S=a^{p^s}+(p-1)a^{p^{s-1}}+(p^2-p)a^{p^{s-2}}+\cdots +(p^s-p^{s-1})a\equiv p(a^{p^{s-1}}+(p-1)a^{p^{s-2}}+(p^2-p)a^{p^{s-3}}+\cdots +(p^{s-1}-p^{s-2})a)$ so by by induction our claim is true. Now assume that $n$ has at least two different prime factors again we prove the claim for this $n$ by induction.assume that $p^s\mid n,p^{s+1}\nmid n$ and write $n=p^sm$ note that: $\sum_{1\le k\le n}a^{(n,k)}=\sum_{d\mid n}\phi (d)a^{\frac{n}{d}}=\sum_{p\nmid d,d\mid n}(a^{p^s})^{\frac{m}{d}}+\sum_{p\mid d,d\mid n}(a^p)^{(\frac{n}{p},\frac{d}{p})}$ as you see I divided the sum(1) into two subsets one of them is a sum of numbers such that $p\mid d$ and the other is the sum of numbers such that $p\nmid d$ both of them are divisible by $m$ according to the induction. so we proved that $m=\frac{n}{p^s}\mid S$(2) now take another prime $q\mid n$(it exist by our assumption) and we prove in similar way that $\frac{n}{q^t}\mid S$(3) where $t$ is exponent of prime $q$ in $n$. combine (2),(3) we get that $n\mid S$. DONE

Now, for the main proof, observe that for each divisor $d \mid n$, the term $a^d$ occurs exactly $\phi\left(\tfrac{n}{d}\right)$ times in the sum $\sum\limits_{k = 1}^n a^{(k, n)}$, because $d = (k, n)$ is equivalent to $\left(\tfrac{k}{d}, \tfrac{n}{d}\right) = 1.$ Furthermore, note that for any prime divisor $p \mid n$ with $v_p(n) = j$, the divisors of $n$ can be partitioned into disjoint sets of the form $\{d, dp, \cdots , dp^j\}$ for each divisor $d \mid n$ with $(d, p) = 1.$ Therefore, it follows that \begin{align*} \sum\limits_{k = 1}^n a^{(k, n)} = \sum\limits_{d \mid n} \phi\left(\frac{n}{d}\right)a^d &= \sum_{\substack{d \mid n \\ (d, p) = 1}} \left[\phi\left(\frac{n}{d}\right)a^d + \phi\left(\frac{n}{dp}\right)a^{dp} + \cdots + \phi\left(\frac{n}{dp^j}\right)a^{dp^j}\right] \\ &= \sum_{\substack{d \mid n \\ (d, p) = 1}} \sum\limits_{k = 0}^j \phi\left(\frac{n}{dp^k}\right)a^{dp^k} \\ &= \sum_{\substack{d \mid n \\ (d, p) = 1}} \sum\limits_{k = 0}^j \phi\left(\frac{n}{dp^j}\right)\phi\left(p^{j - k}\right)a^{dp^k} \\ &= \sum_{\substack{d \mid n \\ (d, p) = 1}} \left[\phi\left(\frac{n}{dp^j}\right)\sum\limits_{k = 0}^j \phi\left(p^{j - k}\right)a^{dp^k}\right]. \end{align*} By the lemma applied to $x = a^d$, it follows that $\sum\limits_{k = 0}^j \phi\left(p^{j - k}\right)a^{dp^k} \equiv 0 \pmod{p^j}.$ Consequently, $\sum\limits_{k = 1}^n a^{(k, n)} \equiv 0 \pmod{p^j}$ as well. Since $p$ was an arbitrary prime divisor of $n$, it follows that $\sum\limits_{k = 1}^n a^{(k, n)}$ is divisible by $n$, as desired. $\square$

Use andria's form, which is $\sum_{d|n} \phi(d) a^{\frac{n}{d}}$. Thus we want to show that $\frac{\sum_{d|n} \phi(d) a^{\frac{n}{d}}}{n}$ is an integer.

Romania is tricky. If this wasn't so well-known, I would salute the problem-writer.

Tiny bug in combinatorial solution above, as you've shown that the result is true for $a \ge 0$ but the combinatorial version fails for the case $a < 0$. An easy patch is to replace $a$ with $a+kn$ for sufficiently large $k$ though (which clearly does not change the residue).

My solution is about the same as that of Dukejukem. I still wish to post it though Observe that for a fixed $d \mid n,$ the number of $k \le n$ such that $d=\gcd(k, n)$ is $\phi \left(\frac{n}{d}\right)$. Accordingly, $$\sum^n_{k=1} a^{\gcd(k, n)}=\sum_{d \mid n} \phi(d)a^{\frac{n}{d}}.$$We will show that the result holds when $n=p^v$ is a prime power. Proceed by induction on $v \ge 1$. For the base case, by FLT, $a+(p-1)a^p \equiv 0 \pmod p$ as required. For the case $v+1$ we see that \begin{align*} \sum^{v+1}_{k=0} \phi(p^k)a^{p^{v+1-k}} =a^{p^{v+1}}+(p-1)a^{p^v}+\sum^{v+1}_{k=2} \phi(p^k)a^{p^{v+1-k}} \equiv pa^{p^v}+ p\left(\sum^{v+1}_{k=2} \phi(p^{k-1})a^{p^{v+1-k}} \right)= p\left(\sum^{v}_{k=0} \phi(p^k)a^{p^{v-k}}\right) \equiv 0 \pmod {p^{v+1}}. \end{align*}Here we used the fact that $a^{p^{v+1}}+(p-1)a^{p^v}=a^{p^v} \cdot \left(a^{\phi(p^{v+1})}+p-1\right) \equiv pa^{p^v} \pmod {p^{v+1}}$ which holds true by Euler's Theorem. For a generic $n$ and any prime $p$ dividing $n$ with $v_p(n)=j,$ we can write $d=p^km$ for $0 \le k \le j$. Fix $m$ and let $b=a^{\frac{n}{p^jm}}.$ From the previous result we get $$\sum_{p^km=d \mid n} \phi(d) a^{\frac{n}{d}}=\phi(m) \cdot \left(\sum^j_{l=0} \phi(p^l)b^{p^{j-l}} \right) \equiv 0 \pmod {p^{j}}.$$Adding over all values of $m$ we see that $p^j$ divides the original sum; and so does $n$ (by repeating this argument for other prime factors of $n$). $\, \square$ EDIT: 1000th post!

In order to reduce the problem to the case $n=p^s$ note that the sum $\sum_{1\le k\le n}a^{(n,k)}=\sum_{d\mid n}\phi (d)a^{\frac{n}{d}}$ is the convolution product of two multiplicative functions, hence it is a multiplicative function in $n$. This is enough in order to consider just the case $n=p^s$.

lol Note that $\frac1n\sum_{k=1}^nx^{(k,n)}$ is a polynomial. It suffices to show that it takes on an integer value when $x=p$ is prime. Rewrite the sum as $\sum_{d\mid n}\varphi\left(\frac nd\right)p^d$, and consider a sequence of integers $a_1,a_2,\ldots$ such that $\sum_{d\mid n}a_d=p^n$ for all $n$. Plugging this into the equation, we want to show that $\sum_{d\mid n}\frac nd\cdot a_d$ is divisible by $n$. We make the stronger claim that $k\mid a_k$ for all $k$. Note that $a_k$ is the number of elements of $\mathbb F_{p^k}$ that are not in $\mathbb F_{p^i}$ for any $i<k$. But any such element must have minimal polynomial in $\mathbb F_p$ of degree $k$. Grouping these elements together by minimal polynomial gives $k\mid a_k$, as desired.

To my astonishment, the sum \[\sum_{j=1}^n\frac{a^{(j,n)}}{\mathrm{e}^{\frac{2\pi\mathrm{i}jk}{n}}}\]is divisible by \(n\) as well. Its proof can be seen here.