Let $\mu(n)$ be the Moebius function. Let $a$ be a positive integer. For odd $n$ (this is possibly true for all $n$, but I only care for odd ones) I get that
$$\sum\_{d|n} \mu\left(\frac{n}{d}\right) a^d \equiv 0 \pmod n.$$
Is there a nice reason for this that can be seen purely from the formula? I have a proof for some special cases of $a$ that uses the particular features of the way I got it, but it would be nice to just be able to see it from the formula.



Why does this formula always give me $0$ modulo $n$?
Your expression, divided by $n$, is the number of aperiodic necklaces of length $n$ with $a$ colors. Since this number is an integer, the sum must be divisible by $n$.


See *Aperiodic necklaces* [here](https://en.wikipedia.org/wiki/Necklace_(combinatorics)?wprov=sfti1).


