285484026

莫比乌斯反演与狄利克雷卷积
前言莫比乌斯反演被大量运用在数论题目中,不少的人在第一次接触到这个东西的时候会被大量的定义概念弄迷。虽然如此,但是...
扫描右侧二维码阅读全文
24
2019/05

莫比乌斯反演与狄利克雷卷积

前言
莫比乌斯反演被大量运用在数论题目中,不少的人在第一次接触到这个东西的时候会被大量的定义概念弄迷。虽然如此,但是本文还是决定先讲清楚概念再讲怎么运用。因为概念和定义在数论进阶和有一定难度的表达式推导中有巨大的作用,所以我写下这篇文章。
第一:帮我自己梳理一下过去大半年在数论方面的学习,以获得一个较为系统的知识体系。
第二:我希望本文可以帮助您学习这个常用的数论技巧,并为后续数论学习打下一个牢靠的基础。


Part1:积性函数及其定义

  1. 数论函数的定义:
    若$f(n)$的定义域为正整数域,值域为负数,则称$f(n)$为数论函数
  2. 积性函数的定义:
    若$f(n)$为数论函数,且f(1) = 1,$对于任意互质的正整数p,q有f(p \cdot q)=f(p) \cdot f(q)$则称$f(n)$为积性函数
  3. 常见的积性函数:
    1.欧拉函数$\phi(n):表示不大于n且于n互质的整数个数$
    2.莫比乌斯函数QQ截图20190524122732.jpg
  4. 完全积性函数的定义:
    若$f(n)$为积性函数,$对于任意的正整数p,q有f(p \cdot q)=f(p) \cdot f(q)$为完全积性函数
  5. 常见的完全积性函数:
    1.幂函数$Id_{k}(n) = d^k$
    2.单位函数QQ截图20190524122708.jpg

Part2:狄利克雷卷积及其定义

  1. 狄利克雷卷积的定义:
    定义两个数论函数$f(x),g(x)的狄利克雷卷积$

$$(f*x)(n) = \sum_{d|n}f(d) \cdot g(\frac{n}{d})$$
$$也记为(f*x) = \sum_{d|n}f(d) \cdot g(\frac{n}{d})$$

  1. 狄利克雷卷积运算的性质:
    1.交换律:$f*g=g*f$
    $$\sum_{d|n}f(d) \cdot g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d}) \cdot g(d)\\$$
    2.结合律:$(f*g)*h=f*(g*h)$

    3.分配律:$f*(g+h)=f*g+f*h$

    4.单位元:$f*\epsilon=f$

  2. 狄利克雷卷积的结果函数:
    $若数论函数f,g,则它们的狄利克雷卷积可以被表示为h=f*g,若f与g均为积性函数,则h为积性函数。$

Part3:莫比乌斯反演
引理1. $\mu*1 = \epsilon$即
$$\sum_{d|n}\mu(d) = \epsilon(n)$$

  1. 莫比乌斯反演:
    如果存在两个函数$F,f$满足

$$F(n)=\sum_{d|n}f(d)$$
则他们也满足
$$f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$$
证明:

\begin{align*} F &= f * 1\\ F*\mu &= f * 1 * \mu\\ F*\mu &= f * \epsilon\\ f &= F*\mu\\ \end{align*}
  1. 莫比乌斯反演的应用:
    求$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]$$
\begin{align*} 设f(d)&=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\\ 设F(d)&=\sum_{i=1}^{n}\sum_{j=1}^{m}[d|gcd(i,j)]\\ F(d)&=\sum_{d|n}f(n)\\ f(n)&=\sum_{d|n}\mu(d)F(\frac{n}{d})\\ \end{align*}\begin{align*} F(d) &= \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[1|gcd(i,j)]\\ F(d) &= \lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor\\ \end{align*}\begin{align*} f(d) &= \sum_{d|x}\mu(x)F(\frac{x}{d}) \\ f(d) &= \sum_{d|x}\mu(x)F(\frac{x}{d}) \\ \end{align*}

原式等于

\begin{align*} \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1] &= \sum_{1|x}\mu(x)F(x) \\ &= \sum_{x=1}^{n}\mu(x)\lfloor \frac{n}{x} \rfloor\lfloor \frac{m}{x} \rfloor \\ \end{align*}
Last modification:May 30th, 2019 at 11:27 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment