定义
设 f(n) 是定义在正整数上的函数,若对于任意互素的正整数 m,n(即 gcd(m,n)=1),均有
f(mn)=f(m)f(n)
则称 f(n) 为积性函数。
若上式对任意正整数 m,n(不要求互素)都成立,则称 f(n) 为完全积性函数。
常见积性函数速查
| 函数 |
记号 |
定义 |
积性类型 |
| 单位函数 |
ε(n) |
[n=1] |
完全积性 |
| 常数函数 |
1(n) |
1 |
完全积性 |
| 恒等函数 |
id(n) |
n |
完全积性 |
| 幂函数 |
idk(n) |
nk |
完全积性 |
| 欧拉函数 |
φ(n) |
1∼n 中与 n 互质的个数 |
积性 |
| 莫比乌斯函数 |
μ(n) |
见莫比乌斯函数章节 |
积性 |
| 除数函数 |
σk(n) |
∑d∣ndk |
积性 |
| 因子个数 |
d(n) |
σ0(n) |
积性 |
| 因子和 |
σ(n) |
σ1(n) |
积性 |
定理 1
若 f(n) 是积性函数且不恒为零,则 f(1)=1。
证明:取 m=n=1,由 gcd(1,1)=1 及积性定义:
f(1)=f(1⋅1)=f(1)⋅f(1)
若 f(1)=0,则对任意 n 有 f(n)=f(n⋅1)=f(n)⋅0=0(平凡零函数)。排除此退化情形,故 f(1)=1。□
定理 2:狄利克雷卷积保持积性
如果 f(n) 与 g(n) 都是积性函数,那么
h(n)=(f∗g)(n)=d∣n∑f(d)g(dn)
也是积性函数。
证明:设 (m,n)=1,需要证明 h(mn)=h(m)h(n)。
h(mn)=(f∗g)(mn)=d∣mn∑f(d)g(dmn)=t1∣m,t2∣n∑f(t1t2)g(t1t2mn).
最后一步用了 (m,n)=1 时 mn 的每个因子可唯一写成 t1t2(t1∣m,t2∣n)。
由于 (t1,t2)=1 且 f,g 是积性函数,
f(t1t2)=f(t1)f(t2),g(t1t2mn)=g(t1m)g(t2n),
其中第二个等式用到 (t1m,t2n)=1。代入得:
h(mn)=t1∣m,t2∣n∑f(t1)f(t2)⋅g(t1m)g(t2n)=t1∣m∑f(t1)g(t1m)⋅t2∣n∑f(t2)g(t2n)=h(m)⋅h(n)
故 h(n) 是积性函数。□
定理 3:狄利克雷卷积的逆元定理
如果 g(n) 和 h(n)=(f∗g)(n) 都是积性函数,则 f(n) 也是积性函数。
证明(反证法):假设 f(n) 不是积性函数,则一定存在一对互素的正整数 (m,n)=1,使得 f(mn)=f(m)f(n)。
在所有这样的 (m,n) 中,选取使得乘积 mn 最小的一对。
由于 h=f∗g 是积性函数,且 (m,n)=1,有 h(mn)=h(m)h(n)。
另一方面,按狄利克雷卷积展开 h(mn)。因为 (m,n)=1,mn 的每个因子可唯一写成 d1d2 的形式(其中 d1∣m,d2∣n):
h(mn)=d∣mn∑f(d)g(dmn)=d1∣m∑d2∣n∑f(d1d2)⋅g(d1m)g(d2n)
从双重求和里把 (d1,d2)=(m,n) 这一项单独提出来:
h(mn)=f(mn)⋅g(1)g(1)+d1∣m,d2∣n(d1,d2)=(m,n)∑f(d1d2)⋅g(d1m)g(d2n)
对于剩余项,因为 d1d2<mn,由”mn 是最小反例”的选取可知 f(d1d2)=f(d1)f(d2)。而 g 是积性函数且 g(1)=1,因此:
h(mn)=f(mn)+d1∣m∑d2∣n∑f(d1)f(d2)⋅g(d1m)g(d2n)−f(m)f(n)=f(mn)+d1∣m∑f(d1)g(d1m)d2∣n∑f(d2)g(d2n)−f(m)f(n)=f(mn)+h(m)h(n)−f(m)f(n)
结合 h(mn)=h(m)h(n),代入上式:
h(m)h(n)=f(mn)+h(m)h(n)−f(m)f(n)
两边消去 h(m)h(n),得:
f(mn)=f(m)f(n)
这与一开始的假设 f(mn)=f(m)f(n) 矛盾。因此不存在反例,f(n) 必须是积性函数。□
定理 4:积性函数的狄利克雷逆也是积性函数
若 f(n) 是积性函数(且 f(1)=0),则其狄利克雷逆 f−1(n) 也是积性函数。
证明:由狄利克雷逆的定义,
(f∗f−1)(n)=ε(n)=[n=1]
ε(n) 显然是积性函数(甚至完全积性)。已知 f(n) 是积性函数,由定理 3(取 g=f、h=ε 均为积性),即得 f−1(n) 是积性函数。□
定理 5:完全积性的充要条件
设 f(n) 是积性函数,则 f(n) 是完全积性函数的充要条件是
f−1(n)=μ(n)⋅f(n)
其中 f−1 是 f 的狄利克雷逆,μ 是莫比乌斯函数。
证明
(⇒)若 f 完全积性,则 f−1=μ⋅f
验证 μ⋅f 恰为 f 的狄利克雷逆:
(f∗(μ⋅f))(n)=d∣n∑μ(d)⋅f(d)⋅f(dn)=d∣n∑μ(d)⋅f(d⋅dn)(f 完全积性)=f(n)d∣n∑μ(d)=f(n)⋅[n=1](μ∗1=ε)=ε(n)
故 f−1=μ⋅f。□
反过来,若 f−1=μ⋅f,则 f 完全积性。
先证一个引理。
引理:在 f−1=μ⋅f 且 f 积性的条件下,对任意素数幂有 f(pα)=f(p)α。
引理证明:由卷积逆的定义 f∗f−1=ε,代入 f−1=μ⋅f:
ε(n)=d∣n∑μ(d)⋅f(d)⋅f(dn)
取 n=pα(α≥1)。pα 的因子中 μ(d)=0 的只有 d=1 和 d=p(含 p2 及以上有平方因子),故:
0=μ(1)f(1)f(pα)+μ(p)f(p)f(pα−1)=f(pα)−f(p)f(pα−1)
因此 f(pα)=f(p)f(pα−1)。递推:
f(pα)=f(p)α−1⋅f(p)=f(p)α
引理证毕。
回到必要性:任取 m,n∈N+,作标准分解(允许指数为零):
m=i=1∏spiai,n=i=1∏spibi,ai,bi≥0
则 mn=∏i=1spiai+bi。由 f 的积性及引理:
f(mn)=f(i=1∏spiai+bi)=i=1∏sf(piai+bi)=i=1∏sf(pi)ai+bi(引理)=i=1∏sf(pi)ai⋅i=1∏sf(pi)bi=i=1∏sf(piai)⋅i=1∏sf(pibi)=f(i=1∏spiai)⋅f(i=1∏spibi)=f(m)⋅f(n)
m,n 任意,故 f 是完全积性函数。□
例题
问题:若 f(n) 是积性函数,证明
f(m)f(n)=f(gcd(m,n))⋅f(lcm(m,n))
其中 gcd(m,n) 是最大公因数,lcm(m,n) 是最小公倍数。
证明:设 m,n 的质因数分解为(允许指数为零)
m=i=1∏spiai,n=i=1∏spibi,ai,bi≥0
则
gcd(m,n)=i=1∏spimin(ai,bi),lcm(m,n)=i=1∏spimax(ai,bi)
由 f 的积性:
f(m)f(n)=(i=1∏sf(piai))(i=1∏sf(pibi))=i=1∏sf(piai)f(pibi)
对每个 i,{ai,bi} 与 {min(ai,bi),max(ai,bi)} 是同一个多重集,因此
f(piai)f(pibi)=f(pimin(ai,bi))f(pimax(ai,bi))
代入得:
f(m)f(n)=i=1∏sf(pimin(ai,bi))f(pimax(ai,bi))=f(i=1∏spimin(ai,bi))⋅f(i=1∏spimax(ai,bi))=f(gcd(m,n))⋅f(lcm(m,n))
证毕。□