贡献者: 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 函数 $\mu:\mathbb{Z}^+\to\{-1, 0, 1\}$ 定义为:
\begin{equation}
\mu(n)=\mu(\prod_{k=1}^r p_k^{f_k})=
\left\{\begin{aligned}
&1 &\quad &(\text{如果}n=1)\\
&(-1)^r &\quad &(\text{如果}f_k=1\text{恒成立})\\
&0 &\quad &(\text{如果有一个}f_k>1)~.
\end{aligned}\right.
\end{equation}
简单来说,一个正整数的质因子中如果有幂次超过 $2$ 的,则它的 Möbius 函数为 $0$;其余情况,则由不同质因子数量的奇偶性决定,奇则为 $-1$,偶则为 $+1$。
Möbius 函数有以下性质:
定理 1 Möbius 的积性
给定互素的正整数 $a, b$,则 $\mu(ab)=\mu(a)\mu(b)$。
只需要检查 $ab, a, b$ 各自的质因数即可得证定理 1 。显然,要求互素是因为,不互素时 $a, b$ 会有公共质因数,此时 $\mu(ab)=0$。
定理 2 求和性质
\begin{equation}
\sum_{d\mid n}\mu(d)=
\left\{\begin{aligned}
&1 \quad (n=1)\\
&0 \quad (n>1)~.
\end{aligned}\right.
\end{equation}
证明:
设 $S$ 是 $n$ 的全体质因子构成的集合($n=1$ 时 $S=\varnothing$)。每个 $d$ 都是 $n$ 的若干质因子求积的结果,而我们只需考虑其中各质因子最多只出现一次的情况。因此,我们所考虑的 $d$,和 $S$ 的子集一一对应,即 $d$ 就是这个子集中各素数相乘的结果。式 2 极为遍历所有 $S$ 的子集的求和。
当 $n=1$ 时,易验证式 2 第一行成立。下设 $n$ 至少有一个质因子。
记 $S=\{a_i\}_{i=1}^r$。则由 $k$ 个 $a_i$ 相乘而得的 $d$,一共有 $C^k_r$ 个,它们均满足 $\mu(d)=(-1)^k$。于是
\begin{equation}
\sum_{d\mid n}\mu(d)=\sum_{k=0}^r(-1)^kC^k_r~.
\end{equation}
又由
二项式定理可知
\begin{equation}
\sum_{k=0}^r(-1)^kC^k_r=(1-1)^r=0~.
\end{equation}
证毕。
需要指出,这其实就是容斥原理的数论形式。
将式 2 作为指数,即得求积的性质:
推论 1 求积性质
任取正实数 $a$,则
\begin{equation}
\prod_{d\mid n}a^{\mu(d)}=
\left\{\begin{aligned}
&a \quad (n=1)\\
&1 \quad (n>1)~.
\end{aligned}\right.
\end{equation}
定理 3 Möbius 反演公式
取映射 $f:\mathbb{Z}^+\to\mathbb{Z}^+$,令 $S(n)=\sum_{d\mid n}f(d)$,$P(n)=\prod_{d\mid n}f(d)$。则有
\begin{equation}
f(n) = \sum_{d\mid n}\mu(d)S \left(\frac{n}{d} \right) ~,
\end{equation}
和
\begin{equation}
f(n) = \prod_{d\mid n} \left(P(\frac{n}{d}) \right) ^{\mu(d)}~.
\end{equation}
证明:
由定理 2 ,$\sum_{dk\mid n}\mu(d)\neq 0$ 当且仅当 $k=n$。于是
\begin{equation}
\begin{aligned}
\sum_{d\mid n}\mu(d)S \left(\frac{n}{d} \right) &=\sum_{d\mid n}\sum_{dk\mid n}\mu(d)f(k)\\
&=\sum_{k\mid n}\sum_{dk\mid n}\mu(d)f(k)\\
&=f(n)~.
\end{aligned}
\end{equation}
由推论 1 ,$\prod_{dk\mid n} \left(f(k) \right) ^{\mu(d)}\neq 1$ 当且仅当 $k=n$。于是
\begin{equation}
\begin{aligned}
\prod_{d\mid n} \left(P(\frac{n}{d}) \right) ^{\mu(d)}&=\prod_{d\mid n} \left(\prod_{dk\mid n}f(k) \right) ^{\mu(d)}\\
&=\prod_{d\mid n}\prod_{dk\mid n} \left(f(k) \right) ^{\mu(d)}\\
&=\prod_{k\mid n}\prod_{dk\mid n} \left(f(k) \right) ^{\mu(d)}\\
&=f(n)~.
\end{aligned}
\end{equation}
证毕。
上述定理中和的形式也适用于一般的数论函数 $f:\mathbb{Z}^+\to\mathbb{R}$ 甚至 $f:\mathbb{Z}^+\to\mathbb{C}$.数论函数像 $S(n)=\sum_{d\mid n}f(d)$ 这样的形式被称为 $f(d)$ 的 Möbius 变换,而 $\sum_{d\mid n}\mu(d)S \left(\frac{n}{d} \right) $ 就是 Möbius 逆变换。作为应用,我们来计算一下几个常见的数论函数的 Möbius 变换并给出一些类似的恒等式。特别重要的是 Euler 函数的 Möbius 变换。
定理 4 Euler 函数的 Möbius 变换
恒等函数 $e(n)=n$ 的 Möbius 逆变换是 Euler 函数 $\varphi(n)$,即有如下恒等式:
\begin{equation}
\varphi(n) = \sum_{d\mid n}\mu(d)\frac{n}{d}~.
\end{equation}
进而,我们得到如下简洁有力的恒等式:
\begin{equation}
\sum_{d\mid n}\varphi(d) = n~.
\end{equation}
证明:
证明是 Möbius 函数求和性质的简单应用。
\begin{equation}
\begin{aligned}
\varphi(n)&=\sum_{1\leq l\leq n,(l,n)=1}1\\
&=\sum_{l=1}^n\sum_{d\mid(l,n)}\mu(d)\\
&=\sum_{l=1}^n\sum_{d\mid l,d\mid n}\mu(d)\\
&=\sum_{d\mid n}\mu(d)\sum_{1\leq l\leq n,d|l}1\\
&=\sum_{d\mid n}\mu(d)\frac{n}{d}~.
\end{aligned}
\end{equation}
定理 5
函数 $u(n)=1,e(n)=n,e_\lambda(n)=n^\lambda$ 的 Möbius 变换分别是除数函数,除数和函数和除数幂和函数 $d(n),\sigma(n),\sigma_\lambda(n)$.
证明由定义直接给出。
为了后面的证明,我们先证明积性函数的 Möbius 变换仍是积性函数。
定理 6 积性函数的 Möbius 变换
若 $f(n)$ 是积性函数,那么 $f(n)$ 的 Möbius 变换仍是积性函数。
证明:
任取互素的整数 $m,n$,我们有
\begin{equation}
\begin{aligned}
\sum_{d\mid m}f(d)\sum_{l\mid n}f(l)&=\sum_{d\mid m}\sum_{l\mid n}f(d)f(l)\\
&=\sum_{d\mid m}\sum_{l\mid n}f(dl)\\
&=\sum_{d\mid mn}f(d)~.
\end{aligned}
\end{equation}
定理 7 von Mangoldt 函数的 Möbius 变换
von Mangoldt 函数 $\Lambda(n)$ 的 Möbius 变换是对数函数 $\log n$,即有如下恒等式:
\begin{equation}
\sum_{d\mid n}\Lambda(n)=\log{n}~.
\end{equation}
证明:
依照积性函数的 Möbius 变换仍是积性函数,我们只需对素数幂证明定理。下令 $n=p^s$.
\begin{equation}
\begin{aligned}
\sum_{d\mid n}\Lambda(n)&=\sum_{l=0}^s \Lambda(p^s)\\
&=\sum_{l=1}^s \log p\\
&=\log p^s\\
&=\log n~.
\end{aligned}
\end{equation}
习题 1
证明 $\mu(n)/n$ 的 Möbius 变换是 $\varphi(n)/n$.