博文目录
回到顶部

前置博文

Skywalkert的博客

abclzr

这些博文写的不错啊，挺好懂的

数论函数

认识几个函数：

莫比乌斯函数 μ

μ(n)={1if n=1(−1)kif n=p1p2p3⋯pk(p1⋯pk为互不相同的质数)0otherwise i.e.当n存在平方因子时

μ 函数也被称作莫比乌斯函数。

性质

性质一    μ 是一个不完全积性函数， 有：

μ(a)⋅μ(b)=μ(a⋅b),当a⊥b

这里 a⊥b 表示 a 与 b 互质。

性质二    当 n 不等于 1 时，n 所有因子的莫比乌斯函数值的和为 0 ，

∑d|nμ(d)=0 , n≠1

当 n=1 时， 上式等于 0 。

性质三    在无穷极限中， 有：

∞∑i=1μ(i)i=0

欧拉函数 φ

φ(n)=1∼n中与n互质的数的个数

通式为：

φ(n)=nk∏i=1(1−1pi)

其中 p1,p2,⋯,pk 为 n 的所有的质因数，且 x≠0。

φ(1)=1

性质

性质一    φ 是一个不完全积性函数，有：

φ(a)⋅φ(b)=φ(a⋅b),当a⊥b

这里 a⊥b 表示 a 与 b 互质。

性质二    当 n 为奇数时， 有：

φ(2n)=φ(n)

当 n 为质数时，有：

φ(n)=n−1

当 n 为大于 2 的正整数时， φ(n) 是偶数。

性质三    有如下柿子：

n∑i=1i[gcd(n,i)=1]=12(n⋅φ(n)+[n=1])

其他数论函数

  1. 1(n)=1， 完全积性

  2. id(n)=n， 完全积性

  3. idk(n)=nk， 完全积性

  4. \(\varepsilon(n) = {1if n=10otherwise\)， 完全积性

  5. σk(n)=∑d∣ndk，表示 n 的约数的 k 次幂的和。

  6. σ(n)=σ1(n)=∑d∣nd， 表示 n 的约数之和。

  7. τ(n)=σ0(n)=∑d∣n1， 表示 n 的约数个数。

狄利克雷卷积

设 f(n),g(n) 是两个数论函数， 他们的狄利克雷卷积定义为：

h(n)=∑d∣nf(d)⋅g(nd)

记为 f∗g。公式也可以这样写：

h(n)=∑ab=nf(a)⋅g(b)

两个数论函数的狄利克雷卷积也是一个数论函数。

性质

  1. 结合律： \(\left( f \ast g \right) \ast h = f \ast \left ( g \ast h \right)\)

  2. 交换律： \(f \ast g = g \ast f\)

未完待续……