Seeking a proof of $\sum_{d|n}\phi(\frac{n}{d})a^d\equiv 0 \mod{n}$, where $\phi$ is the Euler Totient Function.

Question

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}.$$

Answer 1

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.