数论函数
2026-04-21
定义
设 f(n) 为定义在 N+ 上的函数,值域任意(可以为 Z,R,甚至是 C)。
积性函数
若 ∀a,b (amodb=1),都有 f(a×b)=f(a)×f(b),且 f(1)=1,则称 f(n) 为积性函数。
根据定义,显然有 f(n)=∏f(pici)。
常见的积性函数有:
- 欧拉函数 φ(n):[1,n] 中与 n 互质的数的个数。
- 莫比乌斯函数 μ(n):若 n=1,则 μ(n)=1;若存在质数 p 使得 p2∣n,则 μ(n)=0;否则 n 为 k 个不同质数的乘积, μ(n)=(−1)k。
- 约数个数 d(n):n 的正约数个数,即 ∑d∣n1。
- 约数之和 σ(n):n 的正约数之和,即 ∑d∣nd。
完全积性函数
若 ∀a,b∈N+,都有 f(a×b)=f(a)×f(b),且 f(1)=1,则称 f(n) 为完全积性函数。
根据定义,显然有 f(n)=∏f(pici)=∏f(pi)ci。
常见的完全积性函数有:
- 单位函数 ϵ(n):ϵ(n)=[n=1](卷积单位元)。
- 恒等函数 id(n):id(n)=n。
- 常数函数 1(n):1(n)=1。
- 幂函数 Idk(n):Idk(n)=nk。
