浅谈数论函数

数论函数

什么是数论函数？

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

积性函数

什么是积性函数？

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

，人话说就是只要互质，可以乘除的就是积性函数。

可以看出任何积性函数的第1项都是1。否则不满足

而完全积性函数就是：

，人话说就是没有条件，完全可以乘除。

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

几个常见的积性函数

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

2.欧拉函数表示1~i这些正整数中和i互质的数的个数。

3.除数函数表示n的所有约数的k次方和。

引申出来有,即d函数表示该数约数个数，sigma函数表示该数约数和。

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

5.为了方便定义的函数：下文有用。

狄利克雷卷积

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

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

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

满足的性质

1.交换律：

2.结合律：

3.分配律：

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

常见的狄利克雷卷积

1.约数个数

2.约数和

3.莫比乌斯函数的定义

即

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

试证明

设有n个分数分别是

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

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

所以

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

试证明

由4得

莫比乌斯反演的本质

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

形如

即

这才是真正的证明。

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

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

更新于2019.2.20

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

如果，N和M是给定常数，则