Möbius 函数（数论）

贡献者： hfb25; JierPeter

预备知识　数论函数，二项式定理，积性函数

未完成：还可继续添加性质和应用等内容

　　德国数学家 August Ferdinand Möbius 于 1832 年提出 Möbius 函数的概念，这是数论中一个重要的积性函数。Möbius 函数在初等数论和解析数论中随处可见，多以 Möbius 反演的形式出现。

　　任何正整数都可以唯一地分解为其质因数的幂的乘积。比如说， $24 = 2^{3} \times 3$ ， $300 = 2^{3} \times 3 \times 5^{2}$ 。一般地，我们把整数的质因数分解记为 $\prod_{k = 1}^{r} p_{k}^{f_{k}}$ ，其中各 $p_{k}$ 是互不相等的素数，各 $f_{k}$ 都是正整数。Möbius 的概念正是建立在正整数质因数分解上的：

定义 1　Möbius 函数

　　对于任意正整数 $n = \prod_{k = 1}^{r} p_{k}^{f_{k}}$ ，其 Möbius 函数 $μ : Z^{+} \to {- 1, 0, 1}$ 定义为：

\begin{matrix} (1) & μ (n) = μ (\prod_{k = 1}^{r} p_{k}^{f_{k}}) = {\begin{aligned} 1 & (如果 n = 1) \\ (- 1)^{r} & (如果 f_{k} = 1 恒成立) \\ 0 & (如果有一个 f_{k} > 1) . \end{aligned} \end{matrix}

　　简单来说，一个正整数的质因子中如果有幂次超过 $2$ 的，则它的 Möbius 函数为 $0$ ；其余情况，则由不同质因子数量的奇偶性决定，奇则为 $- 1$ ，偶则为 $+ 1$ 。

　　 Möbius 函数有以下性质：

定理 1　Möbius 的积性

　　给定互素的正整数 $a, b$ ，则 $μ (a b) = μ (a) μ (b)$ 。

　　只需要检查 $a b, a, b$ 各自的质因数即可得证定理 1 。显然，要求互素是因为，不互素时 $a, b$ 会有公共质因数，此时 $μ (a b) = 0$ 。

定理 2　求和性质

\begin{matrix} (2) & \sum_{d ∣ n} μ (d) = {\begin{aligned} 1 (n = 1) \\ 0 (n > 1) . \end{aligned} \end{matrix}

　　证明：

　　设 $S$ 是 $n$ 的全体质因子构成的集合（ $n = 1$ 时 $S = \emptyset$ ）。每个 $d$ 都是 $n$ 的若干质因子求积的结果，而我们只需考虑其中各质因子最多只出现一次的情况。因此，我们所考虑的 $d$ ，和 $S$ 的子集一一对应，即 $d$ 就是这个子集中各素数相乘的结果。式 2 极为遍历所有 $S$ 的子集的求和。

　　当 $n = 1$ 时，易验证式 2 第一行成立。下设 $n$ 至少有一个质因子。

　　记 $S = {a_{i}}_{i = 1}^{r}$ 。则由 $k$ 个 $a_{i}$ 相乘而得的 $d$ ，一共有 $C_{r}^{k}$ 个，它们均满足 $μ (d) = (- 1)^{k}$ 。于是

\begin{matrix} (3) & \sum_{d ∣ n} μ (d) = \sum_{k = 0}^{r} (- 1)^{k} C_{r}^{k} . \end{matrix}

又由二项式定理可知

\begin{matrix} (4) & \sum_{k = 0}^{r} (- 1)^{k} C_{r}^{k} = (1 - 1)^{r} = 0 . \end{matrix}

证毕。

　　需要指出，这其实就是容斥原理的数论形式。

　　将式 2 作为指数，即得求积的性质：

推论 1　求积性质

　　任取正实数 $a$ ，则

\begin{matrix} (5) & \prod_{d ∣ n} a^{μ (d)} = {\begin{aligned} a (n = 1) \\ 1 (n > 1) . \end{aligned} \end{matrix}

定理 3　Möbius 反演公式

　　取映射 $f : Z^{+} \to Z^{+}$ ，令 $S (n) = \sum_{d ∣ n} f (d)$ ， $P (n) = \prod_{d ∣ n} f (d)$ 。则有

\begin{matrix} (6) & f (n) = \sum_{d ∣ n} μ (d) S (\frac{n}{d}), \end{matrix}

和

\begin{matrix} (7) & f (n) = \prod_{d ∣ n} {(P (\frac{n}{d}))}^{μ (d)} . \end{matrix}

　　证明：

　　由定理 2 ， $\sum_{d k ∣ n} μ (d) \neq 0$ 当且仅当 $k = n$ 。于是

\begin{matrix} (8) & \begin{aligned} \sum_{d ∣ n} μ (d) S (\frac{n}{d}) & = \sum_{d ∣ n} \sum_{d k ∣ n} μ (d) f (k) \\ = \sum_{k ∣ n} \sum_{d k ∣ n} μ (d) f (k) \\ = f (n) . \end{aligned} \end{matrix}

　　由推论 1 ， $\prod_{d k ∣ n} {(f (k))}^{μ (d)} \neq 1$ 当且仅当 $k = n$ 。于是

\begin{matrix} (9) & \begin{aligned} \prod_{d ∣ n} {(P (\frac{n}{d}))}^{μ (d)} & = \prod_{d ∣ n} {(\prod_{d k ∣ n} f (k))}^{μ (d)} \\ = \prod_{d ∣ n} \prod_{d k ∣ n} {(f (k))}^{μ (d)} \\ = \prod_{k ∣ n} \prod_{d k ∣ n} {(f (k))}^{μ (d)} \\ = f (n) . \end{aligned} \end{matrix}

　　证毕。

　　上述定理中和的形式也适用于一般的数论函数 $f : Z^{+} \to R$ 甚至 $f : Z^{+} \to C$ .数论函数像 $S (n) = \sum_{d ∣ n} f (d)$ 这样的形式被称为 $f (d)$ 的 Möbius 变换，而 $\sum_{d ∣ n} μ (d) S (\frac{n}{d})$ 就是 Möbius 逆变换。作为应用，我们来计算一下几个常见的数论函数的 Möbius 变换并给出一些类似的恒等式。特别重要的是 Euler 函数的 Möbius 变换。

定理 4　Euler 函数的 Möbius 变换

　　恒等函数 $e (n) = n$ 的 Möbius 逆变换是 Euler 函数 $φ (n)$ ，即有如下恒等式：

\begin{matrix} (10) & φ (n) = \sum_{d ∣ n} μ (d) \frac{n}{d} . \end{matrix}

进而，我们得到如下简洁有力的恒等式：

\begin{matrix} (11) & \sum_{d ∣ n} φ (d) = n . \end{matrix}

　　证明：

　　证明是 Möbius 函数求和性质的简单应用。

\begin{matrix} (12) & \begin{aligned} φ (n) & = \sum_{1 \leq l \leq n, (l, n) = 1} 1 \\ = \sum_{l = 1}^{n} \sum_{d ∣ (l, n)} μ (d) \\ = \sum_{l = 1}^{n} \sum_{d ∣ l, d ∣ n} μ (d) \\ = \sum_{d ∣ n} μ (d) \sum_{1 \leq l \leq n, d | l} 1 \\ = \sum_{d ∣ n} μ (d) \frac{n}{d} . \end{aligned} \end{matrix}

定理 5　

　　函数 $u (n) = 1, e (n) = n, e_{λ} (n) = n^{λ}$ 的 Möbius 变换分别是除数函数,除数和函数和除数幂和函数 $d (n), σ (n), σ_{λ} (n)$ .

　　证明由定义直接给出。

　　为了后面的证明，我们先证明积性函数的 Möbius 变换仍是积性函数。

定理 6　积性函数的 Möbius 变换

　　若 $f (n)$ 是积性函数，那么 $f (n)$ 的 Möbius 变换仍是积性函数。

　　证明：

　　任取互素的整数 $m, n$ ，我们有

\begin{matrix} (13) & \begin{aligned} \sum_{d ∣ m} f (d) \sum_{l ∣ n} f (l) & = \sum_{d ∣ m} \sum_{l ∣ n} f (d) f (l) \\ = \sum_{d ∣ m} \sum_{l ∣ n} f (d l) \\ = \sum_{d ∣ m n} f (d) . \end{aligned} \end{matrix}

定理 7　von Mangoldt 函数的 Möbius 变换

　　 von Mangoldt 函数 $Λ (n)$ 的 Möbius 变换是对数函数 $\log n$ ，即有如下恒等式：

\begin{matrix} (14) & \sum_{d ∣ n} Λ (n) = \log n . \end{matrix}

　　证明：

　　依照积性函数的 Möbius 变换仍是积性函数，我们只需对素数幂证明定理。下令 $n = p^{s}$ .

\begin{matrix} (15) & \begin{aligned} \sum_{d ∣ n} Λ (n) & = \sum_{l = 0}^{s} Λ (p^{s}) \\ = \sum_{l = 1}^{s} \log p \\ = \log p^{s} \\ = \log n . \end{aligned} \end{matrix}

习题 1　

　　证明 $μ (n) / n$ 的 Möbius 变换是 $φ (n) / n$ .

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

Möbius 函数（数论）

定义 1 Möbius 函数

定理 1 Möbius 的积性

定理 2 求和性质

推论 1 求积性质

定理 3 Möbius 反演公式

定理 4 Euler 函数的 Möbius 变换

定理 5

定理 6 积性函数的 Möbius 变换

定理 7 von Mangoldt 函数的 Möbius 变换

习题 1

定义 1　Möbius 函数

定理 1　Möbius 的积性

定理 2　求和性质

推论 1　求积性质

定理 3　Möbius 反演公式

定理 4　Euler 函数的 Möbius 变换

定理 5　

定理 6　积性函数的 Möbius 变换

定理 7　von Mangoldt 函数的 Möbius 变换

习题 1　