更新日志:
- 2023/10/15:发布文章
一、前置芝士
- 积性函数
- 卷积
二、定义
-
对于两个数论函数 \(f(x),g(x)\) 的狄利克雷卷积的结果 \(h(x)\) 定义为 \(h(x) = \sum_{d|x} f(d)g(\frac x d)\),简记为 \(h = f*g\)
-
特别地,由于 \(\epsilon\) 卷上任何函数时函数不变,所以 \(\epsilon\) 为
狄利克雷卷积
的单位元
三、性质
- 交换律:\(f*h = g*f\)
- 结合律:\((f*g)*h = f*(g*h)\)
- 分配律:\((f+g)*h = f*h+g*h\)
- \(\forall f(x) \neq 0\),有且只有一个在狄利克雷卷积意义下下的逆元
- 两个积性函数的狄利克雷卷积为积性函数
- 积性函数的逆元为积性函数
四、函数与狄利克雷卷积
① \(~\epsilon = \mu*1\Longleftrightarrow\epsilon(n) = \sum\limits_{d|n}\mu(d)~\)
prove:
设\(~n = \prod p_i^{k_i},n'=\prod p_i~\),\(~n~\)的质因子个数为\(~m~\)
\[\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)=\sum_{i=0}^{m}\binom m i(-1)^i=(1+(-1))^m \]即当且仅当\(~m = 0~\)(\(~n = 1~\))时\(~\sum\limits_{d|n}\mu(d)=1~\)