默比乌斯反演公式

默比乌斯反演(Möbius inversion)是数论中一个重要的公式,用于解决求和问题。给定两个数论函数 $f(n)$ 和 $g(n)$,如果它们满足以下关系:

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

其中求和是在所有整数 $d$ 上进行的,满足 $d$ 是 $n$ 的因子(即 $d | n$)。那么,默比乌斯反演公式给出了另一个关系,即:

$$g(n) = \sum_{d | n} \mu(d) f\left(\frac{n}{d}\right)$$

这里,$\mu(d)$ 是默比乌斯函数(Möbius function),它根据整数 $d$ 的不同素因子的个数来定义:

1、如果 $d$ 是一个正平方数的倍数(即含有某个素因子的平方),则 $\mu(d) = 0$。

2、如果 $d$ 是 $k$ 个不同素数的乘积,且 $k$ 为偶数,则 $\mu(d) = 1$。

3、如果 $d$ 是 $k$ 个不同素数的乘积,且 $k$ 为奇数,则 $\mu(d) = -1$。

默比乌斯反演公式在数论中有许多应用,例如在求解数论函数的和、研究算术函数的性质等方面。