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 函数 $\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$.

                     

© 小时科技 保留一切权利