I need to prove the proposition.
Let $a$ be an arbitrary integer. Then for every positive integer $n$, we have $$\sum_{d \mid n}\phi\left(\frac{n}{d}\right)a^d\equiv0\pmod{n}.$$
I need to prove the proposition.
Let $a$ be an arbitrary integer. Then for every positive integer $n$, we have $$\sum_{d \mid n}\phi\left(\frac{n}{d}\right)a^d\equiv0\pmod{n}.$$
I suspect the poster is asking for an elementary solution, which this isn't. Anyway.
The cycle index of the cyclic group on $n$ elements is $$ Z(C_n) = \frac{1}{n} \sum_{d|n} \phi(n/d) x_{n/d}^d $$ where the $x_d$ are the variables.
Hence, by the Polya Enumeration Theorem, the quantity $$ Z(C_n)_{x_1 = a, x_2 = a, x_3 = a, \ldots} $$ counts the number of distinct necklaces on $n$ elements under rotation where the slots on the necklace hold one of $a$ colors.
Hence, combinatorially, the following quantity must be an integer $$ \frac{1}{n} \sum_{d|n} \phi(n/d) a^d$$ because it counts the number of necklaces.
There is more at Wikipedia.
Let $p$ be a prime divisor of $n$. Let $\frac{n}{p^{v_p(n)}}=m$.
Now by partitioning the divisors by the $p$-adic order, we have $$\sum_{d|n} \phi (\frac{n}{d})a^d = \sum_{x|n,(x,p)=1} \sum_{i=0}^{v_p(n)} \phi (\frac{n}{xp^i}) \cdot a^{xp^i}= \sum_{x|m} \sum_{i=0}^{v_p(n)} \phi (p^{v_p(n)-i} \cdot \frac{m}{x}) \cdot a^{xp^i}=$$ $$ \sum_{x|m} \sum_{i=0}^{v_p(n)} \phi (p^{v_p(n)-i} ) \cdot \phi (\frac{m}{x})a^{xp^i} = \sum_{x|m} \phi (\frac{m}{x}) \sum_{i=0}^{v_p(n)} \phi(p^{v_p(n)-i})a^{xp^i} $$
It suffices to show that (by replacing $a^x$ by $a$ and $v_p(n)$ with $n$) for all $n$ we have $$\sum_{i=0}^{n} \phi(p^{n-i})a^{p^i} \equiv 0 \pmod{p^{n}}$$
After proving this, we can use this for all primes and we will be done.
We proceed with induction. For $n=1$, we have $\phi(p) a + \phi(1) a^p \equiv (p-1)a+ a \equiv 0 \pmod{p}$.
Assume that this is true for $k-1$. We show that this is true for $k$ as well.
We have $$a^{p^k} + (p-1)a^{p^{k-1}} + p(p-1) a^{p^{k-2}} + \cdots $$ $$= a^{p^k} + (p-1)a^{p^{k-1}} + p((p-1)a^{p^{k-2}} + p(p-1)a^{p^{k-3}} + \cdots ) $$ $$=a^{p^k} + (p-1)a^{p^{k-1}} + p(\text{something divisible by } p^{k-1} - a^{p^{k-1}}) \text{ (by induction hypothesis)}$$ $$=a^{p^k}-a^{p^{k-1}} + \text{something divisible by } p^k \equiv 0 \pmod{p^k}$$ as desired. We are done. $\blacksquare$