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.

  • $\begingroup$ 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 $\endgroup$ Nov 18, 2022 at 22:53
  • $\begingroup$ 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.$) $\endgroup$ Nov 18, 2022 at 23:24

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .