# Which arithmetic functions satisfy $\sum_{d \mid n} f(\frac{n}{d}) k^d \equiv 0 \pmod{n}$ for all positive integers $n,k$?

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.

• In the language of arithmetic functions, this is, if $e_k(n)=k^n,$ that $(f*e_k)(n)$ is always divisible by $n.$ Now, if $I(n)=n,$ $\mu* I=\phi.$ If $h$ is a function such that $h(n)$ is always divisible by $n,$ then $I*h$ has the same property. So if $f$ has your property then $I*f$ has your property. In particular, since $\phi=I*\mu,$ the property from $\phi$ follows from the property for $\mu.$ Here, $*$ is the Dirichlet convolution. en.wikipedia.org/wiki/Dirichlet_convolution Nov 18, 2022 at 22:53
• Given any function $g:\mathbb N\to \mathbb Z$ we can define $$f(n)=\sum_{d\mid n} d\mu(n/d)g(d).$$ This gives uncountably many such functions, include $\mu(n)$ (with $g(1)=1, g(n)=0$ for $n>1,$) and $\phi(n),$ (with $g_0(n)=1$ for all $n.$) Nov 18, 2022 at 23:24

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