莫比乌斯反演
直接上结论：
若有
则有
简而言之就是
若 (g=f*1) , 则有 (f=mu*g) ((“*”)为狄利克雷卷积)
若看懂了就可直接到文章末尾：莫比乌斯反演的另一种形式。
前置知识
零:([P])艾弗森括号
(P)为一命题:
([P]=egin{cases} 1 命题为真\ 0 命题为假 end{cases})
一：数论函数
本文的函数都是指数论函数，其定义域为非负整数，值域为实数(一般为正整数).
(f(n), g(n)) 为数论函数, 定义其运算：
-
(f(n) + g(n) = (f + g)(n))
-
(x×f(n)=(x imes f)(n))
二：狄利克雷卷积
定义狄利克雷卷积为 (“*”), (f*g) 叫这两个函数的卷积
狄利克雷卷积的性质:
- 交换律( f*g=g*f)
- 结合律( (f*g)*h=f*(g*h))
- 分配律( (f+g)*h=f*h+g*h)
- 不知道什么律 ( x imes (f*g)=(x imes f)*g)
以上性质请自行证明.
三：(1(n)) 与 (epsilon(n))
定义 (1(n)=1), 1是一个数论函数.
- 性质： ((f*1)(n)=sum_{d|n}f(d) imes 1(frac{n}{d})=sum_{d|n}f(d))
定义数论函数 (epsilon(n)=[n=1])
- 性质： ((epsilon * f)=f)
- 证明：
((epsilon * f)(n))
(=sum_{d|n}f(d) imesepsilon(frac{n}{d}))
当(n为1)时，显然成立.
当(n>1)时，
(=sum_{d|n,d e n}f(d) imes 0 + f(n) imes1)
(=f(n))
四：(mu(n))
定义莫比乌斯函数(mu=egin{cases}(-1)^t, n=p_1 imes p_2 ... p_t 且 p_i 互不相同\ 0, others end{cases})
定理：(mu * 1=epsilon)
证明：
((mu * 1)(n))
(=sum_{d|n}mu(d))
(n=1) 时显然成立,
(n>1) 时，(omega(n)) 为 n 质因子中互不相同的数的个数
(=sum_{i=0}^{omega(n)}C_{omega(n)}^{i} imes (-1)^i) （考虑贡献）
(=sum_{i=0}^{omega(n)}C_{omega(n)}^{i} imes (-1)^i imes (1)^{(omega(n)-i)})
由二项式定理：((a+b)^m=sum_{i=0}^{m}C_m^ia^ib^{(m-i)})
则原式(=(-1+1)^{omega(n)}=0), 证毕.
至此，我们可以来证明了
若有
则有
证明：
即证明若 (g=f*1) , 则有 (f=mu*g)
将(g=f*1)带人，
(mu*g=mu*(f*1)=(1*mu)*(f)=epsilon * f=f)
证毕
莫比乌斯反演的另一种形式：
一：定义运算 (foplus g) :
这里的除法不是整除！！！（保证 (j) 为 (i) 的倍数）
或者也可以写成：
注意这东西是没有交换律的。
(epsilon oplus f = f) (自己证明一下)
二：与狄利克雷卷积 (“ * ”) 的关系：
证明：
三：反演
有上面那个结论就很好证明了：