There are $$\frac{1}{n} \sum_{d \mid n} \varphi\left(\frac{n}{d}\right) \cdot k^d$$ different $k$-ary necklaces of length $n$ as a result of Pólya's enumeration theorem, where $\varphi$ is Euler's totient function. Furthermore, exactly $$\frac{1}{n} \sum_{d \mid n} \mu\left(\frac{n}{d}\right) \cdot k^d$$ of these necklaces are aperiodic, where $\mu$ is the Möbius function. Thus, one is tempted to ask:
Which arithmetic functions $f: \mathbb{N} \to \mathbb{C}$ satisfy $$\sum_{d \mid n} f(\frac{n}{d}) k^d \equiv 0 \pmod{n}$$ for all positive integers $n,k$?
In the language of Dirichlet convolutions, we are looking for arithmetic functions $f$ for which $(f * p_k)(n)$ is an integer divisible by $n$ for all positive integers $n, k$ where $p_k(n) = k^n$. What can we say about such functions? Are there other interesting examples besides $\varphi$ and $\mu$? Is it possible to determine all of them, perhaps at least those with range $\mathbb{Z}$ instead of $\mathbb{C}$?
As a side note, I came across these identities while trying to generalize the combinatorial proof of Fermat's little theorem to Euler's theorem in the form $k^n \equiv k^{n-\varphi(n)} \pmod{n}.$ I find it frustrating that the proof doesn't work in the general case, and there isn't any known combinatorial interpretation of Euler's theorem yet.
We will say a function $h$ is "divisible" if $h(n)$ is always divisible by $n.$
If $g_1,g_2$ are divisible, then $$(g_1*g_2)(n)=\sum_{d\mid n} g_1\left(\frac nd\right)g_2(d)$$ is also divisible, where $*$ is the Dirichlet convolution.
If you define $e_k(n)=k^n,$ you are asking for what $f$ is $f*e_k$ divisible for all $k.$
Since convolution is associative, given any $f$ with your property and any divisible function $g,$ you get $g*f$ has your property, because $(g*f)*e_k=g*(f*e_k).$
Now, there are a lot of divisible functions $g.$ Given any $g_0:\mathbb N\to \mathbb Z,$ $g(n)=ng_0(n)$ is divisible, and hence $$f(n)=(\mu*g)(n)=\sum_{d\mid n}\mu(n/d)dg_0(d)$$
And this gives uncountable many functions $f.$
So there are a lot of such functions.
But by Möbius inversion, $f*e_1=g$ is divisible, so all functions $f$ which have your property come from some $g_0.$
So $f*e_k$ is divisible for all $k\geq1$ if and only if $f*e_1$ is divisible, if and only if $f=\mu* g$ for some divisible $g.$