Number of $k$-tuples of elements generating a cyclic group

Question

Let $k$, $m$ be natural numbers, and $C_m:=\mathbb{Z}/ m \mathbb{Z}$ be the cyclic group of order $m$.

Let $N_{k, \, m}$ be the cardinality of the following set: $$\{(a_1, \ldots, a_k) \in (C_m)^k \; | \; \text{the subset } \{a_1, \ldots, a_k\} \text{ generates } C_m \}.$$

Question. Is a closed formula for $N_{k,\, m}$ known? If so, what is a reference?

Clearly $$N_{k, \, m} \geq m^k - (m- \phi(m))^k,$$ with equality when $m=p$ is a prime number, in which case $$N_{k, \, p} = p^k -1.$$ But what about the general situation? This looks to me as a natural problem, so I suspect that the answer is well-known to the people working in the field. However, I am not an expert in Combinatorics, so I may be missing some elementary solution.

Any answer and/or reference to the relevant literature will be appreciated.

Answer 1

I believe the answer is $\sum_{d\mid m}d^k\mu(m/d)$ where $\mu$ is the Möbius function. The reason is that $C_m$ has a unique subgroup of order $d$ for each divisor $d$ of $m$, and we can partition the $m^k$ $k$-tuples by the subgroup they generate. So, if $f(n)$ is the number of $k$-tuples generating $C_n$, then we should get $m^k=\sum_{d\mid m} f(d)$ and hence, by Möbius inversion, $f(m)=\sum_{d\mid m}d^k\mu(m/d)$.

Added. As pointed out by @SamHopkins, this problem was essentially solved by P. Hall for general finite groups using the Möbius function for the subgroup lattice, but for cyclic groups nothing that fancy is needed. The general argument is basically the same. You can count $k$-tuples by the subgroups they generate. So if $\Lambda(G)$ is the subgroup lattice of $G$ and $f(H)$ is the number of $k$-tuples of elements of $H$ generating $H$, then you have that $|G|^k = \sum_{H\leq G}f(H)$ and so $f(G) = \sum_{H\leq G}|H|^k\mu(H,G)$ where $\mu$ is the Möbius function of $\Lambda(G)$. For a cyclic group, this boils down to the classical number theoretic Möbius function and inversion formula.