莫比乌斯函数:莫比乌斯函数:莫比乌斯函数:
(1)若d=1,则μ(d)=1(1)若d=1,则\mu(d)=1(1)若d=1,则μ(d)=1
(2)若d=p1∗p2∗⋯∗pk,其中pi(1≤i≤k)为互异的素数,则μ(d)=(−1)k(2)若d=p_1*p_2*\cdots*p_k,其中p_i(1\leq i \leq k)为互异的素数, 则\mu(d)=(-1)^k(2)若d=p1∗p2∗⋯∗pk,其中pi(1≤i≤k)为互异的素数,则μ(d)=(−1)k
(3)其余情况μ(d)=0(3)其余情况\mu(d)=0(3)其余情况μ(d)=0
莫比乌斯反演:莫比乌斯反演:莫比乌斯反演:
f(k)=∑d∣kg(d)⇒g(k)=∑d∣kf(kd)μ(d)f(k)=\sum^{}_{d|k}g(d)\Rightarrow g(k)=\sum^{}_{d|k}f(\frac{k}{d})\mu(d)f(k)=d∣k∑g(d)⇒g(k)=d∣k∑f(dk)μ(d)
f(k)=∑k∣dd≤nf(d)⇒g(k)=∑k∣dd≤nf(dk)μ(d)f(k)=\sum^{d\leq n}_{k|d}f(d)\Rightarrow g(k)=\sum^{d\leq n}_{k|d}f(\frac{d}{k})\mu(d)f(k)=k∣d∑d≤nf(d)⇒g(k)=k∣d∑d≤nf(kd)μ(d)
莫比乌斯函数性质:莫比乌斯函数性质:莫比乌斯函数性质:
(1)对于任意正整数n,有:∑d∣nμ(d)={1,若n=10,若n>1(1)对于任意正整数n,有:\sum^{}_{d|n}\mu(d)=\left\{\begin{array}{cc}1,若n=1\\0,若n>1\end{array}\right.(1)对于任意正整数n,有:∑d∣nμ(d)={1,若n=10,若n>1
(2)对于任意正整数n,有∑d∣nμ(d)d=φ(n)n(2)对于任意正整数n,有\sum^{}_{d|n}\frac{\mu(d)}{d}=\frac{\varphi(n)}{n}(2)对于任意正整数n,有∑d∣ndμ(d)=nφ(n)
(3)莫比乌斯函数μ(n)是积性函数(3)莫比乌斯函数\mu(n)是积性函数(3)莫比乌斯函数μ(n)是积性函数