Proving $\sum d\mu \left(\frac{n}{d}\right) = \frac{\mu\left(\frac{n}{(m,n)}\right)}{\phi \left(\frac{n}{(m, n)}\right)}\phi(n)$.

Question

I came across the formula $\sum_{d|\text{gcd}(m,n)} d\mu \left(\frac{n}{d}\right) = \frac{1}{\phi \left(\frac{n}{\text{gcd}(m, n)}\right)}\mu\left(\frac{n}{\text{gcd}(m,n)}\right)\phi(n)$, where $m,n \in \mathbb{N}$ and $d$ is a divisor of $\text{gcd}(m,n)$. I'm aware this eventually reduces to a counting argument, and that, given the Moebius $\mu$ function on the left-hand side, only the divisors $d$ that result in $\frac{n}{d}$ being a product of distinct primes (i.e. no prime factor having an exponent greater than one) contribute something to the sum, but how can I cleverly count the terms of the sum to show they add up to the right-hand side?

Answer 1

A possible approach is to show that $n\mapsto f(n):=\sum_{d\,\mid\,(m,n)}d\mu(n/d)$ is a multiplicative function (with $m$ considered fixed). As the RHS of the formula is a multiplicative function of $n$ (since $\phi$, $\mu$ and $n\mapsto(m,n)$ are), it just remains (afterwards) to prove the formula for $n=p^k$ a prime power, which is easy.

For the former, we represent $f$ as a Dirichlet convolution of two multiplicative functions: $$f(n)=\sum_{d\,\mid\,n}g(d)\mu(n/d),\qquad g(n):=\begin{cases}n,&n\mid m\\0,&n\nmid m\end{cases}$$ (the multiplicativity of $g$ is easy to check; as of $\mu$, it is well-known). Thus, $f$ is multiplicative.

Now if $n=p^k$ and $p^r\mid m$ with the largest possible $r\geqslant 0$, then $(m,n)=p^{\min\{k,r\}}$ and $$f(p^k)=\sum_{j=0}^{\min\{k,r\}}p^j\mu(p^{k-j})=\begin{cases}\hfill 0,\hfill&r<k-1\\\hfill-p^{k-1},\hfill&r=k-1\\p^k-p^{k-1},&r>k-1\end{cases}.$$ This coincides with the RHS of the formula being proven. Indeed, let $q=n/(m,n)$.

If $r>k-1$ then $q=1$ and $\phi(n)\mu(q)/\phi(q)=\phi(n)=\phi(p^k)=p^k-p^{k-1}$.

Otherwise $q=p^{k-r}$, and $\mu(q)=0$ if $r<k-1$. Finally, if $r=k-1$, then $q=p$ and $$\phi(n)\mu(q)/\phi(q)=(p^k-p^{k-1})(-1)/(p-1)=-p^{k-1}.$$

---

Update. H&W go a simpler way. With $g=(m,n)$ and $q=n/g$ (again), $$\sum_{d\,\mid\,g}d\mu(n/d)=\sum_{d\,\mid\,g}(g/d)\mu\big(n/(g/d)\big)=g\sum_{d\,\mid\,g}\mu(qd)/d=\ldots$$ [now $\mu(qd)=\mu(q)\mu(d)$ if $(d,q)=1$, and $\mu(qd)=0$ otherwise] $$\ldots=\mu(q)g\sum_{\substack{d\,\mid\, g\\(d,q)=1}}\frac{\mu(d)}{d}=\mu(q)g\prod_{\substack{p\,\mid\,g\\p\,\nmid\,q}}\left(1-\frac1p\right)=\mu(q)\frac{n}{q}\prod_{\substack{p\,\mid\,n\\p\,\nmid\,q}}\left(1-\frac1p\right),$$ clearly equal to the desired $\mu(q)\phi(n)/\phi(q)$.