课程目录
本页目录
狄利克雷卷积
两个数论函数 f,g 的狄利克雷卷积定义为:
(f∗g)(n)=d∣n∑f(d)g(dn)
基本性质:
- 交换律:f∗g=g∗f
- 结合律:(f∗g)∗h=f∗(g∗h)
- 单位元:ε(即 f∗ε=f),其中 ε(n)=[n=1]
- 若 f(1)=0,则 f 存在唯一的狄利克雷逆 f−1,满足 f∗f−1=ε
证明
交换律
(f∗g)(n)=d∣n∑f(d)g(dn)=d∣ndd′=n∑f(d′n)g(d′)=d′∣n∑g(d′)f(d′n)=(g∗f)(n)
结合律
需要证明 (f∗g)∗k=f∗(g∗k)。
设 A(n)=(f∗g)(n),则
(A∗k)(n)=a∣n∑A(a)k(an)=a∣n∑[(f∗g)(a)]k(an)=a∣n∑b∣a∑f(b)g(ba)k(an)=abc=n∑f(a)g(b)k(c).
设 B(n)=(g∗k)(n),同理
(f∗B)(n)=a∣n∑f(a)B(an)=a∣n∑f(a)b∣n/a∑g(b)k(abn)=abc=n∑f(a)g(b)k(c).
两式相等,故 (f∗g)∗k=f∗(g∗k)。□
定理 1
I(n)=[n1]
对于所有的数论函数,均有 (f∗I)(n)=f(n)
证明:
(f∗I)(n)=a∣n∑f(a)⋅I(an)=a∣n∑f(a)⋅[na]=a∣n∑(f(a)⋅[na]={f(n)0a=na<n)=f(n)□
定理 2
设 f 是数论函数且 f(1)=0。则存在唯一的数论函数 f−1,称为 f 的狄利克雷逆,使得
(f∗f−1)(n)=I(n),
且
f−1(n)=⎩⎨⎧f(1)1,−f(1)1d∣nd=n∑f(dn)f−1(d),n=1,n>1.
证明
当 n=1 时,
(f∗f−1)(1)=f(1)f−1(1)=I(1)=1.
由 f(1)=0 得 f−1(1)=1/f(1),且这个值唯一。
假设结论对所有小于 n 的正整数成立,下证对 n 也成立。因为 n>1 时 I(n)=0,
0=I(n)=(f∗f−1)(n)=d∣n∑f−1(d)f(dn)=d∣nd=n∑f−1(d)f(dn)+f−1(n)f(1).
移项得
f−1(n)=−f(1)1d∣nd=n∑f−1(d)f(dn).□
欧拉—莫比乌斯关系的卷积表述
以下两条恒等式是整个初等数论最核心的结论,用卷积写出来既简洁又便于推导:
φ∗1=idμ∗1=ε
第一条的证明:(φ∗1)(n)=∑d∣nφ(d)=n=id(n)。
第二条的证明:(μ∗1)(n)=∑d∣nμ(d)=[n=1]=ε(n)。
从这两条出发,可以流水般推出其他关系:
| 关系 |
推导 |
| φ=μ∗id |
φ=φ∗ε=φ∗(1∗μ)=(φ∗1)∗μ=id∗μ |
| id=φ∗1 |
已证明 |
| 1∗μ=ε |
已证明 |
| φ(n)=n∑d∣ndμ(d) |
φ=μ∗id 展开即得 |