Jordan's totient function $J_{k}(n)$ is a generalization of Euler's totient function that counts the number of $k$-tuples $(a_1, \ldots, a_k)$ for which $1 \leq a_1, \ldots, a_n \leq n$ and $gcd(a_1, \ldots, a_k, n) = 1$, where $n$ and $k$ are positive integers. There is an explicit formula for this function as follows: $$J_{k}(n) = n^k \prod_{p} \left(1 – \frac{1}{p^k}\right),$$ where $p$ ranges over through the prime divisors of $n$. Using this identity, it is pretty straightforward to deduce that $J_{1}(n)$, which is Euler's totient function, divides $J_{k}(n)$ for all positive integers $k$ and $n$. However, given the simplicity of the definitions, I believe there is a much more elegant combinatorial proof of this fact that does not rely on the explicit formula. I would be glad if anyone could provide a combinatorial proof or trick that I'm unable to see.
Is there a combinatorial proof that Euler’s totient function divides Jordan’s totient function
arithmetic-functionscombinatorial-proofstotient-function
Best Answer
Equivalently, $J_k(n)$ counts the $k$-tuples $(a_1,\cdots,a_k)$ of elements of $\mathbb{Z}/n\mathbb{Z}$ which generate the whole ring (as an ideal). We can verify $(\mathbb{Z}/n\mathbb{Z})^\times$ acts freely on these tuples by multiplication: if $(a_1,\cdots,a_k)$ is fixed under multiplication by $u$, and $r_1a_1+\cdots+r_ka_k=1$, then
$$ u = u(r_1a_1+\cdots+r_ka_k)=r_1(ua_1)+\cdots+r_k(ua_k)=r_1a_1+\cdots+r_ka_k=1, $$
i.e. $u=1$. Since $\varphi(n)=|(\mathbb{Z}/n\mathbb{Z})^\times|$, this shows $\varphi(n)\mid J_k(n)$.
What I don't see is why $d\mid k$ would imply $J_d(n)\mid J_k(n)$ in general, though.