博客

浅谈数论函数

  • Post author:
  • Post category:其他


数论函数

什么是数论函数？

定义域在正整数的函数。（下文如无特殊说明均为数论函数）

积性函数

什么是积性函数？

积性函数即满足这个性质的数论函数：

f(n)=f(a)f(b)[gcd(a,b)=1,ab=n]
，人话说就是只要互质，可以乘除的就是积性函数。


可以看出任何积性函数的第1项都是1。

否则不满足
f(1)=f(1)f(1)

而完全积性函数就是：

f(n)=f(a)f(b)[ab=n]
，人话说就是没有条件，完全可以乘除。

只要能满足这样的东西就行。

几个常见的积性函数

1.莫比乌斯函数
\mu
的取值后面再说

2.欧拉函数
\varphi(n)=\sum_{i=1}^n[gcd(i,n)=1]
表示1~i这些正整数中和i互质的数的个数。

3.除数函数
\sigma_k(n)=\sum_{d|n}d^k
表示n的所有约数的k次方和。

引申出来有
d(n)=\sigma_0(n),\sigma(n)=\sigma_1(n)
,即d函数表示该数约数个数，sigma函数表示该数约数和。

4.单位函数：
e(n)=\epsilon(n)=[n=1]
,即n=1（红字性质）时等于1，反之为0.后面那个叫艾普西隆，英文epsilon。

5.为了方便定义的函数：
I(n)=1,Id(n)=n;
下文有用。

狄利克雷卷积

狄利克雷卷积是一种运算方式（吧）？对于乘法性狄利克雷卷积，它的性质就是：

(f*g)(x)=\sum_{d|x}f(d)g(\frac{x}{d})

注意*表示“卷”而不是乘。乘法表示是什么都不写或者·或者x。

人话说就是，两个积性函数指定项的卷积即枚举其因数，用第一个函数的因数项和另一个函数的另一个因数项相乘再求和。

满足的性质

1.交换律：
f*g=g*f

2.结合律：
f*g*h=f*(g*h)

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


4.单位元：
f*\epsilon=\epsilon*f=f
，即任何积性函数卷积艾普西隆就是自己。

常见的狄利克雷卷积


1.约数个数

d(n)=I(n)*I(n)=\sum_{d|n}I(d)I(\frac{n}{d})=\sum_{d|n}1


2.约数和

\sigma_1(n)=I(n)*Id(n)=\sum_{d|n}I(d)Id(\frac{n}{d})=\sum_{d|n}d



3.莫比乌斯函数的定义

\mu(n)*I(n)=\epsilon(n)

即

\sum_{d|n}\mu(d)=[n=1]


4.Id函数由欧拉函数所得的卷积

试证明

n=Id(n)=\varphi(n)*I(n)=\sum_{d|n}\varphi(d)

设有n个分数分别是

\frac{1}{n},\frac{2}{n},\frac{3}{n}...\frac{n-1}{n},\frac{n}{n}

其中有的分数可以约分为最简分数。可以看出约分后的分母是n的约数

且由于这时这个分母与分子互质且这个分母比n小，所以对于每个分母a会出现
\varphi(a)
次。

所以

n=Id(n)=\sum_{d|n}\varphi(d)


5.欧拉函数的一种卷积方式

试证明

\varphi=\mu*Id

由4得

Id=\varphi*I

\mu*Id=\varphi*(I*\mu)

\because\mu*I=\epsilon

\therefore\mu*Id=\varphi

莫比乌斯反演的本质

狄利克雷卷积的最大特点就是这样的函数都可以线性筛求出来。有了狄利克雷卷积，我们就可以说说莫比乌斯反演的本质了。

形如

g(n)=\sum_{d|n}f(d)=f(n)*I(n)

即

g=f*I

\therefore\mu*g=f*I*\mu

\therefore\mu*g=f

\therefore f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})
这才是真正的证明。

至于后缀和形式，那是另一种证明方式，这里贴一张图上来。(注：图中f与g的意义与本文相反。）

这才是莫比乌斯函数与莫比乌斯反演的意义。要先明确莫比乌斯函数的定义，再谈反演。

更新于2019.2.20

对于有种后缀和形式的莫比乌斯反演，还有更重要的另一种表示方法：

如果
f(n)=\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=n]
，N和M是给定常数，则

g(n)=\sum_{n|d}f(d)=\sum_{n|d}\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j)=d]=\sum_{i=1}^N\sum_{j=1}^M[n|gcd(i,j)]=\sum_{i=1}^{\left \lfloor \frac{N}{n}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{M}{n} \right \rfloor}[1|gcd(i,j)]=\sum_{i=1}^{\left \lfloor \frac{N}{n} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{M}{n} \right \rfloor}1={\left \lfloor \frac{N}{n} \right \rfloor}{\left \lfloor \frac{M}{n} \right \rfloor}


版权声明：本文为qq_42835815原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。