How to show that $\sum_{d\mid n} \gcd(d,k) \mu(n/d)=0$?

137 Views Asked by At

Fix $k\in \Bbb{N}$ such that $k > 1$. Define $f_k(n)=\gcd(n,k)$ for $\forall\ n \geq 1$. Let $\mu$ denote the Möbius function. Notice that $$\sum_{d\mid n}f_k(d)\mu\left(\frac{n}{d}\right)=0$$ for all $n>k$ (and more generally, for all $n$ that don't divide $k$).

But I can not prove it.

1

There are 1 best solutions below

1
On

We denote $f(n):=\sum_{d|n}f_k(d)\mu\left(\frac{n}{d}\right)$. For $\gcd(n,m)=1$ we have \begin{align} f(n)f(m) &=\sum_{d|n}f_k(d)\mu\left(\frac{n}{d}\right)\sum_{e|m}f_k(e)\mu\left(\frac{m}{e}\right) \\&=\sum_{d|n}\sum_{e|m}f_k(d)f_k(e)\mu\left(\frac{n}{d}\right)\mu\left(\frac{m}{e}\right) \\&=\sum_{d|n}\sum_{e|m}f_k(de)\mu\left(\frac{n}{d}\frac{m}{e}\right) \\&=\sum_{d|nm}f_k(d)\mu\left(\frac{nm}{d}\right) \\&=f(nm). \end{align} For prime $p$ such that $p^n\nmid k$ we have $f_k(p^n)=f_k(p^{n-1})$, so \begin{align} f(p^n) &=\sum_{d|p^n}f_k(d)\mu\left(\frac{p^n}{d}\right) \\&=\sum_{i=0}^nf_k(p^i)\mu(p^{n-i}) \\&=f_k(p^{n-1})\mu(p)+f_k(p^n)\mu(1) \\&=0. \end{align} Here we can forget about $i<n-1$ because then $\mu(p^{n-i})=0$. The last equality follows from $\mu(p)=-1$ and $\mu(1)=1$.

For all $n>k$ there exists a prime that divides $n$ more times than $k$, so by the two properties we just proved, we find $f(n)=0$.