sum of gcd(k,n)

hbghlyj

$$\sum_{k=1}^n \gcd(k,n)=\sum_{d|n} d \,\phi(n/d)=\sum_{d|n} d \, \tau(d) \, \mu(n/d)$$

恒等式来自math.stackexchange.com/questions/135351/sum-of-gcdk-n
第一个等号
$$\sum_{k=1}^n \gcd(k,n)=\sum_{d|n}\sum_{\array{1≤k≤n\\\gcd{(k,n)=d}}}d=\sum_{d|n}\sum_{\array{1≤k'≤\frac nd\\\gcd{(k',\frac nd)=1}}}d=\sum_{d|n}d\,\phi(n/d)$$
第二个等号如何证明呢?应该会用到Mobius inversion

tommywong

我覺得將$\displaystyle \sum_{d\mid n} d\phi(n/d)$換成$\displaystyle
\sum_{d\mid n} d \tau(d)\mu(n/d)$沒有任何好處
代入實例時由處理一個函數變成要處理兩個函數了

$\displaystyle \phi(n)=\sum_{d\mid n}\mu(d)(n/d)=\sum_{d\mid n}d\mu(n/d)$
$\displaystyle \tau(n)=\sum_{d\mid n}1$

這裡我想了兩個方法：

$\displaystyle \sum_{d\mid n} d\phi(n/d)$
$\displaystyle =\sum_{d\mid n} d \sum_{d'\mid (n/d)}\mu(d')(n/dd')$
$\displaystyle
=\sum_{d\mid n} \sum_{d'\mid (n/d)}\mu(d')(n/d')$
$\displaystyle
=\sum_{d'\mid n} \sum_{d\mid (n/d')}\mu(d')(n/d')$
$\displaystyle
=\sum_{d'\mid n}\mu(d')(n/d')\tau(n/d')$
$\displaystyle
=\sum_{d\mid n} d \tau(d)\mu(n/d)$

$\displaystyle \sum_{d\mid n} d\phi(n/d)$
$\displaystyle =\sum_{d\mid n} \sum_{d'\mid (n/d)}dd'\mu(n/dd')$
$\displaystyle =\sum_{d\mid D} \sum_{D\mid n}D\mu(n/D)$
$\displaystyle =\sum_{D\mid n}D\tau(D)\mu(n/D)$