常用积性函数:
\(\bullet\) 单位函数 \(\varepsilon(n)\text{ = }\begin{cases}\text{1, while n=1}\\\text{0, otherwise}\end{cases}\)
\(\bullet\) 幂函数 \(\begin{cases}Id_k(x)\text{ = }x^k\\Id(x)\text{ = }x\text{, }k\text{ = }1\\1(x)\text{ = }1\text{, }k\text{ = }0\end{cases}\)
\(\circ\) 除数函数 \(\begin{cases}\sigma_k(n)\text{ = }\Sigma_{d\mid{n}}\text{ }d^k\\\sigma(n)\text{ = }\Sigma_{d\mid{n}}\text{ }d\text{, }k\text{ = }1\end{cases}\)
\(\circ\) 欧拉函数 \(\varphi(n)\text{ = }\Sigma_{i = 2}^n\text{ }\left[n\perp i\right]\)
其中 \(\bullet\) 表示完全积性函数
因为这些都是积性函数,它们都满足 \(f(1) = 1\)
(我们常用 \(f, g, h\) 来代表积性函数
狄利克雷卷积
狄利克雷卷积是定义在数论函数间的二元运算。
定义式为:
以下出现的 \(*\) 不是我们常理解的乘,而是卷
也会写为:
且若 \(f,g\) 是积性函数,则 \(f * g\) 也是积性函数
特殊函数的卷积:
- \(Id_k * 1\text{ = }\sigma_k\)
- \(\varphi * 1\text{ = }Id\)
性质:
交换律: \(f * g = g * f\)
结合律: \((f * g) * h = f * (g * h)\)
分配律: \(f * (g + h) = f * g + f * h\)
分配律只在函数加法下有效
单位元:
\((\varepsilon * f)(n)\text{ = }\Sigma_{xy = n}\text{ }\varepsilon(x)f(y)\text{ = }f(n)\) ,所以单位函数 \(\varepsilon\) 是狄利克雷卷积的单位元
逆元:
若 \(f * g\text{ = }\varepsilon\) ,则称 \(g\) 是 \(f\) 的狄利克雷逆元,记作 \(f^{-1}\)。
可证明 \(f^{-1}\) 是积性函数