[莫比乌斯反演学习笔记]

形式一:

设函数$$F(n)=\Sigma_{d|n}f(d)$$

那么$$f(n)=\Sigma_{d|n}\mu (\frac{n}{d})\times F(s)$$

形式二:

设函数$$F(d)=\Sigma_{d|n}f(n)$$

那么$$f(d)=\Sigma_{d|n}\mu (\frac{n}{d})\times F(n)$$

定义:

$\Sigma_{d|n}\mu (d)={1|n=1,0|n>1}$

性质:

一、若$f$是在互质下的积性函数,那么$F$也是。

二、$\Sigma_{d|n}\frac{\mu (d)}{d}=\frac{\phi (n)}{n}$

证明:

预备知识:

$e$卷积单位元:$e(1)=1,e(x>1)=0$

$I$乘法单位元:$I(x)=1$

$c(x)=x$

狄利克雷卷积证明:

莫比乌斯函数$\mu$是$I$在卷积意义下的逆元,也就是$\mu \times I = e$

展开可以得到$\Sigma_{d|n}\mu (d)=e(n)$——————(定义)

通常,莫比乌斯函数$\mu$定义为:

$\mu (1)=1$

$\mu(n)=(-1)^{k} |当n为k个不同的素数乘积$

$\mu(n)=0|其他情况$

当$n=1$,定义成立。

当$n!=1$,有$n=q_1^{a_1}q_2^{a_2}…q_k^{a_k}$

那么$$\Sigma_{d|n}\mu (d)=\mu (1)+\mu (q_1)+\mu (q_2)+…+\mu (q_k)+\mu (q_1\times q_2)+…+\mu (q_1\times q_2\times … \times q_k)$$

$$=C(k,0)+C(k,1)\times (-1)^{1}+C(k,2)\times (-1)^2+…+C(k,k)\times (-1)^k$$

$$=[1+(-1)]^{k}=0$$

定义成立。

综上,这里的$\mu$满足定义。

 

对于性质一:

$$F(n)=\Sigma_{d|n}f(d)=\Pi_{i=1}^{k}\Sigma_{j=0}^{a_i}f(q_i^j)$$

$$=\Pi_{i=1}^{k}F(q_i^{a_i})$$

证毕。

对于性质二:

$$\Sigma_{d|n}\frac{\mu (d)}{d}=\frac{\phi (n)}{n}$$

$$\Sigma_{d|n}\frac{n}{d}\mu (d)=\phi (n)$$

$$(c\times \mu)(n)=\phi (n)$$

$$(c\times \mu \times I)(n)=(\phi \times I)(n)$$

$$n=\Sigma_{d|n}\phi (d)$$

$$令F(n)=\Sigma_{d|n}\phi(d)$$

性质一可得:

$$F(n)=\Pi_{i=1}^{k}F(q_i^{a_i})$$

$$F(n)=\Pi_{i=1}^{k}\Sigma_{j=1}^{a_i}(q_i-1)\times q_i^{j-1}$$

$$F(n)=\Pi_{i=1}^{k}q_i^{a_i}$$

$$\phi(n)=F(n)=n$$

证毕。

关于“[莫比乌斯反演学习笔记]”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注