Seeking a proof of $\sum_{d|n}\phi(\frac{n}{d})a^d\equiv 0 \mod{n}$, where $\phi$ is the Euler Totient Function. 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}.$$
 A: 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.
A: 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$
