Dirichlet 卷积学习笔记
定义
定义数论函数 \(f,g\)，则他们的 \(Dirichlet\) 卷积为
\[(f*g)(x)=\sum_{d|x}f(d)\cdot g(\frac xd)=\sum_{d|x}f(\frac xd)\cdot g(d) \]性质
\[f*g=g*f\tag{1} \] \[f*(g+h)=f*g+f*h\tag{2} \] \[(f*g)*h=f*(g*h)\tag{3} \]证明如下：
- \(f*g=g*f\)
- \(f*(g+h)=f*g+f*h\)
- \((f*g)*h=f*(g*h)\)
单位元函数
\[\varepsilon(x)=[x=1]=\begin{cases}1&x=1\\0&x\neq 1\end{cases} \]性质
任意一个数论函数 \(f\) 与 \(\varepsilon\) 的卷积为该函数本身，即 \(f*\varepsilon=f\)
证明：
\[\begin{aligned}(f*\varepsilon)(x)&=\displaystyle\sum_{d|x}f(d)\cdot \varepsilon(\frac xd)\\&=\sum_{d|x\&d\neq x}f(d)\cdot \varepsilon(\frac xd)+f(x)\cdot \varepsilon(1)\\&=f(x)\end{aligned} \]常见数论函数
-
\(1(x)=1\)，常函数
-
\(id(x) = x\)，常函数
-
\(id^k(x)=x^k\)，常函数的一般形式
-
\(\varepsilon(x)=[n=1]\)，单位元函数
-
\(\varphi(x)=\displaystyle\sum_{i=1}^{x}[gcd(i,x)==1]=n\prod_{i=1}^c(1-\frac1{p_i})\)，欧拉函数
-
\(d(x)=\displaystyle\sum_{i|x}1\)，约数个数
-
\(\sigma(x)=\displaystyle\sum_{i|x}i\)，约数和
-
\(\lambda(x)=(-1)^x\)
-
设 \(x=\displaystyle\prod_{i=1}^{c}p_i^{k_i}\)，其中 \(p_i\) 为质数，莫比乌斯函数
性质及证明
\(1.\ d=1*1\)
\[\begin{aligned}(1*1)(x)&=\displaystyle\sum_{d|x}1(d)\cdot 1(\frac xd)\\&=\sum_{d|x}1\\&=d(x)\end{aligned} \]\(2.\ 1=\mu*d\)
\[\begin{aligned}\mu*d&=\mu*1*1\\&=\varepsilon*1\\&=1\end{aligned} \]\(3.\ \sigma=id*1\)
\[\begin{aligned}(id*1)(x)&=\displaystyle\sum_{d|x}id(d)\cdot 1(\frac xd)\\&=\sum_{d|x}d\\&=\sigma(x)\end{aligned} \]\(4.\ \varepsilon=1*\mu\)
\[\begin{aligned}(1*\mu)(x)&=\displaystyle\sum_{d|x}1(\frac xd)\cdot \mu(d)\\&=\sum_{d|x}\mu(d)\end{aligned} \]-
当 \(x = 1\) 时，\(\displaystyle\sum_{d|x}\mu(d)=\mu(1)=1=\varepsilon(x)\)
-
当 \(x>1\) 时，令 \(x=\displaystyle\prod_{i=1}^{c}p_i^{k_i}\)，则有 \(\displaystyle\sum_{d|x}=\sum_{i=0}^{k}(-1)^iC_k^i=C_k^0-C_k^1+C_k^2-\cdots+(-1)^kC_k^k\)
证明方法①
\(k\) 为奇数时，由杨辉三角对称性易知成立
\(k\) 为偶数时，原式 \(=C_{k-1}^{0}-C_{k-1}^0+C_{k-1}^1-C_{k-1}^1+\cdots+C_{k-1}^{k-1}-C_{k-1}^{k-1}=0\)
证明方法②
原式 \(=\displaystyle\sum_{i=0}^{k}C_n^ix^iy^{k-i}=(x+y)^k\)
令 \(x=1,y=-1\)，原式得证.
\(5.\ id=\varphi*1\)
\[\begin{aligned}(\varphi*1)(x)&=\displaystyle\sum_{d|x}\varphi(d)\cdot 1(\frac xd)\\&=\sum_{d|x}\varphi(d)\end{aligned} \]即证：\(x=\displaystyle\sum_{d|x}\varphi(d)\)
由于 \(\varphi\) 是一个积性函数，因此只需证明 \(x=p^k\) （\(p\) 为质数）时满足条件即可。
\[\begin{aligned}\displaystyle\sum_{d|p^k}\varphi(d)&=\sum_{i=0}^k\varphi(p^i)\\&=1+\sum_{i=1}^kp^i*(1-\frac 1p)\\&=1+\sum_{i=1}^k(p^i-p^{i-1})\\&=p^k\end{aligned} \]得证
\(6.\ \varphi=id*\mu\)
\[\begin{aligned}id*\mu&=\varphi*\mu*1\\&=\varphi*\varepsilon\\&=\varphi\end{aligned} \]\(7.\ id=\sigma*\mu\)
\[\begin{aligned}\sigma*\mu&=id*1*\mu\\&=\varphi*1\\&=id\end{aligned} \]\(8.\ \sigma=\varphi*d\)
\[\begin{aligned}\varphi*d&=id*\mu*d\\&=id*1\\&=\sigma\end{aligned} \]