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

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?

• It would be helpful if you clarified the dependence of the left hand side on $m$. Jul 6 '20 at 1:18
• That's partly what confused me. $m$ only appears on the left-hand side in the form of $d$, which is a divisor of $\text{gcd}(m,n)$. Jul 6 '20 at 1:19
• @user30293 Since $m$ is basically arbitrary, and $\gcd(m,n) \mid n$, you can baically replace $\gcd(m,n)$ in all $3$ places with any factor of $n$. As such, the formula is equivalent to saying that for any positive integer $j \mid n$, you have $\sum_{d|j}d\mu \left(\frac{n}{d}\right) = \frac{1}{\phi\left(\frac{n}{j}\right)}\mu\left(\frac{n}{j}\right)\phi(n)$. Jul 6 '20 at 1:57
• @JohnOmielan I see. The way I understood it, the $\phi(n)$ on the RHS just counts the number of integers less than $n$ that are coprime to $n$. The $\mu\left(\frac{n}{j}\right)$ takes care of the sign, but what about the $\phi\left(\frac{n}{j}\right)$? Where does that come in? Jul 6 '20 at 2:06
• @user30293 I don't know offhand how to prove the formula, including about how that fraction, or where $\phi\left(\frac{n}{j}\right)$, applies. I just wanted to explain how the use of $m$ here in the $\gcd(m,n)$ statement can be simplified to the equivalent formula I gave. Jul 6 '20 at 2:06

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&rk-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. 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)$$.