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?

  • 1
    $\begingroup$ It would be helpful if you clarified the dependence of the left hand side on $m$. $\endgroup$ Jul 6 '20 at 1:18
  • $\begingroup$ 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)$. $\endgroup$
    – user30293
    Jul 6 '20 at 1:19
  • $\begingroup$ @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)$. $\endgroup$ Jul 6 '20 at 1:57
  • $\begingroup$ @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? $\endgroup$
    – user30293
    Jul 6 '20 at 2:06
  • $\begingroup$ @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. $\endgroup$ 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&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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.