Möbius函数(数论)

                     

贡献者: 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}

   证毕


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

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利