莫比乌斯反演(从入门到自闭)

数论函数

定义域在正整数上的函数称为数论函数。

积性函数

若对于任意的互质的一对数$x$和$y$，有$f(x\times y)=f(x)\times f(y)$，则称函数$f$为积性函数。

卷积

$(f* g)(n)$称为函数$f$与$g$的卷积。

$$(f* g)(n)=\sum\limits_{\tau = -\infty}^{\infty}f(\tau)g(n-\tau)$$

狄利克雷卷积

若$f$和$g$都为数论函数，则$(f* g)(n)$称为数论函数$f$与$g$的狄利克雷卷积。

$$(f* g)(n)=\sum\limits_{d\ |\ n}f(d)g(\dfrac{n}{d})$$

性质

卷积运算满足交换律、结合律和分配律。

积性函数的卷积仍为积性函数。

单位元

定义数论函数$\varepsilon(n)=[n=1]$，它是狄利克雷卷积的单位元。
若$f$为数论函数，则

$$(f*\varepsilon)(n)=(\varepsilon* f)(n)=\sum\limits_{d|n}\varepsilon(d)f(\dfrac{n}{d})=f(n)$$

从上式可以看出，在狄利克雷卷积的运算中，单位元就相当于实数运算中的$1$。

莫比乌斯函数

定义

$\mu(n)$为莫比乌斯函数。

$$\sum\limits_{d\ |\ n}\mu(d)=[n=1]$$

性质

将$n$质因数分解$n=p_1^{a_1}p_2^{a_2}…p_{\varphi(n)}^{a_{\varphi(n)}}$，则:

$$\mu(n)=\begin{cases}1&n=1\\ (-1)^{\varphi(n)}&\prod a_i=1\\ 0&otherwise\end{cases}$$

---

莫比乌斯函数是积性函数。

$$\mu(x\times y)=\mu(x)\times\mu(y)\ \ \ \gcd(x,y)=1$$

---

$$\sum\limits_{d\ |\ n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n}$$

---

$\mu$与$1$互为逆元。

$$\mu * 1=\sum\limits_{d|n}\mu(d)=[n=1]=\varepsilon(n)$$

莫比乌斯反演

定理

若数论函数$f$与$g$满足

$$f(n)=\sum\limits_{d\ |\ n}g(d)$$

则

$$g(n)=\sum\limits_{d\ |\ n}\mu(\dfrac{n}{d})f(d)=\sum\limits_{d\ |\ n}\mu(d)f(\dfrac{n}{d})$$

证明

$$\because f=g*1$$ $$\therefore f\ast\mu = g\ast1\ast\mu = g\ast(1\ast\mu) = g\ast\varepsilon = g$$ $$\therefore g=f*\mu=\sum\limits_{d|n}f(d)\mu(\dfrac{n}{d})$$ $$\text{又}\because f*\mu=\mu*f,\mu*f=\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d})$$ $$\therefore g(n)=\sum\limits_{d\ |\ n}\mu(\dfrac{n}{d})f(d)=\sum\limits_{d\ |\ n}\mu(d)f(\dfrac{n}{d})$$