目录
1 积性函数
定义
定理1
2 Möbius变换及逆变换
定义
数论函数
f
(
n
)
、
F
(
n
)
f(n)、F(n)
f
(
n
)
、
F
(
n
)
，若
F
(
n
)
=
∑
d
∣
n
f
(
d
)
=
∑
d
∣
n
f
(
n
d
)
F(n)=\sum_{d|n}f(d)=\sum_{d|n}f(\frac{n}{d})
F
(
n
)
=
d
∣
n
∑
f
(
d
)
=
d
∣
n
∑
f
(
d
n
)
则称
F
(
n
)
F(n)
F
(
n
)
是
f
(
n
)
f(n)
f
(
n
)
的Möbius变换，称
f
(
n
)
f(n)
f
(
n
)
是
F
(
n
)
F(n)
F
(
n
)
的Möbius逆变换。
定理2
设
f
(
n
)
f(n)
f
(
n
)
是给定的数论函数，
F
(
n
)
F(n)
F
(
n
)
是它的Möbius变换，且
n
=
p
1
α
1
⋯
p
r
α
r
n=p_1^{\alpha_1} \cdots p_r^{\alpha_r}
n
=
p
1
α
1
⋯
p
r
α
r
，那么
-
F(
n
)
=
f
(
1
)
F(n)=f(1)
F
(
n
)
=
f
(
1
)
，当
n>
1
n>1
n
>
1
时，
F(
n
)
=
∑
e
1
=
0
α
1
⋯
∑
e
r
=
0
α
r
f
(
p
1
e
1
⋯
p
r
e
r
)
F(n)=\sum_{e_1=0}^{\alpha_1} \cdots \sum_{e_r=0}^{\alpha_r}f(p_1^{e_1} \cdots p_r^{e_r})
F
(
n
)
=
e
1
=
0
∑
α
1
⋯
e
r
=
0
∑
α
r
f
(
p
1
e
1
⋯
p
r
e
r
)
-
若
f(
n
)
f(n)
f
(
n
)
是积性函数，则
F(
n
)
F(n)
F
(
n
)
也是积性函数，且当
n>
1
n>1
n
>
1
时，
F(
n
)
=
∏
i
=
1
r
(
1
+
f
(
p
i
)
+
⋯
+
f
(
p
i
α
i
)
)
=
∏
p
α
∣
n
(
1
+
f
(
p
)
+
⋯
+
f
(
p
α
)
)
F(n)= \prod_{i=1}^{r}\left(1+f(p_i)+\cdots +f(p_i^{\alpha_i}) \right) = \prod_{p^\alpha|n}\left(1+f(p)+\cdots +f(p^{\alpha}) \right)
F
(
n
)
=
i
=
1
∏
r
(
1
+
f
(
p
i
)
+
⋯
+
f
(
p
i
α
i
)
)
=
p
α
∣
n
∏
(
1
+
f
(
p
)
+
⋯
+
f
(
p
α
)
)
-
若
f(
n
)
f(n)
f
(
n
)
是完全积性函数，则
F(
n
)
=
∏
i
=
1
r
(
1
+
f
(
p
i
)
+
⋯
+
f
α
i
(
p
i
)
)
=
∏
p
α
∣
n
(
1
+
f
(
p
)
+
⋯
+
f
α
(
p
)
)
F(n)= \prod_{i=1}^{r}\left(1+f(p_i)+\cdots +f^{\alpha_i}(p_i) \right) = \prod_{p^\alpha|n}(1+f(p)+\cdots +f^{\alpha}(p))
F
(
n
)
=
i
=
1
∏
r
(
1
+
f
(
p
i
)
+
⋯
+
f
α
i
(
p
i
)
)
=
p
α
∣
n
∏
(
1
+
f
(
p
)
+
⋯
+
f
α
(
p
)
)
证明
- （略）
-
因为
f(
n
)
f(n)
f
(
n
)
是积性函数，因此
F(
n
)
=
∑
e
1
=
0
α
1
⋯
∑
e
r
=
0
α
r
f
(
p
1
e
1
)
⋯
f
(
p
r
e
r
)
=
{
∑
e
1
=
0
α
1
f
(
p
1
e
1
)
}
⋯
{
∑
e
r
=
0
α
r
f
(
p
r
e
r
)
}
=
F
(
p
1
α
1
)
⋯
F
(
p
r
α
r
)
F(n)=\sum_{e_1=0}^{\alpha_1} \cdots \sum_{e_r=0}^{\alpha_r}f(p_1^{e_1}) \cdots f(p_r^{e_r})=\left\{\sum_{e_1=0}^{\alpha_1}f(p_1^{e_1})\right\} \cdots\left\{\sum_{e_r=0}^{\alpha_r}f(p_r^{e_r})\right \}=F(p_1^{
{\alpha}_1})\cdots F(p_r^{
{\alpha}_r})
F
(
n
)
=
e
1
=
0
∑
α
1
⋯
e
r
=
0
∑
α
r
f
(
p
1
e
1
)
⋯
f
(
p
r
e
r
)
=
{
e
1
=
0
∑
α
1
f
(
p
1
e
1
)
}
⋯
{
e
r
=
0
∑
α
r
f
(
p
r
e
r
)
}
=
F
(
p
1
α
1
)
⋯
F
(
p
r
α
r
)
-
因为
f(
n
)
f(n)
f
(
n
)
是完全积性函数，因此
F(
n
)
=
∑
e
1
=
0
α
1
⋯
∑
e
r
=
0
α
r
f
e
1
(
p
1
)
⋯
f
e
r
(
p
r
)
=
{
∑
e
1
=
0
α
1
f
e
1
(
p
1
)
}
⋯
{
∑
e
r
=
0
α
r
f
e
r
(
p
r
)
}
F(n)=\sum_{e_1=0}^{\alpha_1} \cdots \sum_{e_r=0}^{\alpha_r}f^{e_1}(p_1) \cdots f^{e_r}(p_r)=\left\{\sum_{e_1=0}^{\alpha_1}f^{e_1}(p_1)\right\} \cdots\left\{\sum_{e_r=0}^{\alpha_r}f^{e_r}(p_r)\right \}
F
(
n
)
=
e
1
=
0
∑
α
1
⋯
e
r
=
0
∑
α
r
f
e
1
(
p
1
)
⋯
f
e
r
(
p
r
)
=
{
e
1
=
0
∑
α
1
f
e
1
(
p
1
)
}
⋯
{
e
r
=
0
∑
α
r
f
e
r
(
p
r
)
}
常见的Möbius变换
f
(
n
)
1
n
φ
(
n
)
μ
(
n
)
μ
(
n
)
/
n
F
(
n
)
τ
(
n
)
σ
(
n
)
n
I
(
n
)
φ
(
n
)
/
n
\begin{array}{c|ccccc} f(n) & \text{1} & \text{n} & \text{$\varphi(n)$} & \text{$\mu(n)$} & \text{$\mu(n)/n$} \\ \hline F(n) & \tau(n) &\sigma(n) & n & I(n) & \varphi(n)/n \\ \end{array}
f
(
n
)
F
(
n
)
1
τ
(
n
)
n
σ
(
n
)
φ
(
n
)
n
μ
(
n
)
I
(
n
)
μ
(
n
)
/
n
φ
(
n
)
/
n
-
除数个数函数
τ(
n
)
=
∑
d
∣
n
1
\tau(n)=\sum_{d|n}1
τ
(
n
)
=
∑
d
∣
n
1
-
除数和函数
σ(
n
)
=
∑
d
∣
n
d
\sigma(n)=\sum_{d|n}d
σ
(
n
)
=
∑
d
∣
n
d
-
莫比乌斯函数
μ(
n
)
\mu(n)
μ
(
n
)
-
μ(
n
)
=
{
1
d
=
1
(
−
1
)
r
d
=
p
1
⋯
p
r
0
其
他
\mu(n)= \begin{cases} 1 & d=1 \\ (-1)^r & d=p_1 \cdots p_r \\ 0 & 其他 \end{cases}
μ
(
n
)
=
⎩
⎪
⎨
⎪
⎧
1
(
−
1
)
r
0
d
=
1
d
=
p
1
⋯
p
r
其
他
-
若(
d
1
，
d
2
)
=
1
，
则
μ
(
d
1
⋅
d
2
)
=
μ
(
d
1
)
⋅
μ
(
d
2
)
若(d_1，d_2)=1，则 \mu(d_1\cdot d_2)=\mu(d_1)\cdot \mu(d_2)
若
(
d
1
，
d
2
)
=
1
，
则
μ
(
d
1
⋅
d
2
)
=
μ
(
d
1
)
⋅
μ
(
d
2
)
-
-
单位函数
I(
n
)
=
∑
d
∣
n
μ
(
d
)
I(n)=\sum_{d|n}\mu(d)
I
(
n
)
=
∑
d
∣
n
μ
(
d
)
I(
n
)
=
∑
d
∣
n
μ
(
d
)
=
[
n
=
1
]
=
{
1
n
=
1
0
n
>
1
I(n)=\sum_{d|n}\mu(d)=[n=1]= \begin{cases} 1 & \text{$n=1$} \\ 0 & \text{$n>1$} \\ \end{cases}\quad
I
(
n
)
=
d
∣
n
∑
μ
(
d
)
=
[
n
=
1
]
=
{
1
0
n
=
1
n
>
1
例题
-
例1：求
μ2
(
n
)
/
φ
(
n
)
\mu^2(n)/\varphi(n)
μ
2
(
n
)
/
φ
(
n
)
的Möbius变换
F(
n
)
F(n)
F
(
n
)
解
：
∵∑
d
∣
p
α
μ
2
(
d
)
/
φ
(
d
)
=
1
+
1
p
⋅
(
1
−
1
p
)
=
p
p
−
1
=
1
1
−
1
p
\because \quad \sum_{d|{p^{\alpha}}}\mu^2(d)/\varphi(d)=1+\frac{1}{p\cdot (1-\frac{1}{p})}=\frac{p}{p-1}=\frac{1}{1-\frac{1}{p}}
∵
d
∣
p
α
∑
μ
2
(
d
)
/
φ
(
d
)
=
1
+
p
⋅
(
1
−
p
1
)
1
=
p
−
1
p
=
1
−
p
1
1
又∵
μ
2
(
n
)
、
φ
(
n
)
、
μ
2
(
n
)
/
φ
(
n
)
是
积
性
函
数
又 \because \quad \mu^2(n)、\varphi(n)、\mu^2(n)/\varphi(n) 是积性函数
又
∵
μ
2
(
n
)
、
φ
(
n
)
、
μ
2
(
n
)
/
φ
(
n
)
是
积
性
函
数
∴F
(
n
)
=
∑
d
∣
p
1
α
1
⋯
p
r
α
r
μ
2
(
d
)
/
φ
(
d
)
=
1
1
−
1
p
1
⋯
1
1
−
1
p
r
=
n
φ
(
n
)
\therefore \quad F(n)= \sum_{d|{p_1^{
{\alpha}_1}}\cdots{p_r^{
{\alpha}_r}}}\mu^2(d)/\varphi(d)=\frac{1}{1-\frac{1}{p_1}}\cdots \frac{1}{1-\frac{1}{p_r}}=\frac{n}{\varphi(n)}
∴
F
(
n
)
=
d
∣
p
1
α
1
⋯
p
r
α
r
∑
μ
2
(
d
)
/
φ
(
d
)
=
1
−
p
1
1
1
⋯
1
−
p
r
1
1
=
φ
(
n
)
n
-
例2：设
n=
p
1
α
1
⋯
p
r
α
r
，
n=p_1^{\alpha_1} \cdots p_r^{\alpha_r}，
n
=
p
1
α
1
⋯
p
r
α
r
，
求
Ω(
n
)
\Omega(n)
Ω
(
n
)
的Möbius变换
F(
n
)
F(n)
F
(
n
)
.-
不同的素因数个数函数，非积性函数
ω(
n
)
=
{
r
n
>
1
0
n
=
1
\omega(n) = \begin{cases} r & \text{$n>1$}\\ 0 & \text{$n=1$}\\ \end{cases} \quad\quad\quad
ω
(
n
)
=
{
r
0
n
>
1
n
=
1
-
素因数个数函数，非积性函数
Ω(
n
)
=
{
α
1
+
⋯
+
α
r
n
>
1
0
n
=
1
\Omega(n) = \begin{cases} \alpha_1+\cdots + \alpha_r & \text{$n>1$} \\ 0 & \text{$n=1$} \\ \end{cases}\quad
Ω
(
n
)
=
{
α
1
+
⋯
+
α
r
0
n
>
1
n
=
1
-
除数个数函数，积性函数
τ(
n
)
=
τ
(
p
1
α
1
⋯
p
r
α
r
)
=
(
1
+
α
1
)
(
1
+
α
2
)
⋯
(
1
+
α
r
)
\tau(n)=\tau(p_1^{\alpha_1} \cdots p_r^{\alpha_r})=(1+\alpha_1)(1+\alpha_2)\cdots(1+\alpha_r)
τ
(
n
)
=
τ
(
p
1
α
1
⋯
p
r
α
r
)
=
(
1
+
α
1
)
(
1
+
α
2
)
⋯
(
1
+
α
r
)
解1：
F(
n
)
=
∑
e
1
=
0
α
1
⋯
∑
e
r
=
0
α
r
Ω
(
p
1
e
1
⋯
p
r
e
r
)
=
∑
e
1
=
0
α
1
⋯
∑
e
r
=
0
α
r
(
e
1
+
e
2
+
⋯
+
e
r
)
F(n) =\sum_{e_1=0}^{\alpha_1} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_1^{e_1} \cdots p_r^{e_r}) =\sum_{e_1=0}^{\alpha_1} \cdots \sum_{e_r=0}^{\alpha_r}(e_1+e_2+\cdots + e_r)
F
(
n
)
=
e
1
=
0
∑
α
1
⋯
e
r
=
0
∑
α
r
Ω
(
p
1
e
1
⋯
p
r
e
r
)
=
e
1
=
0
∑
α
1
⋯
e
r
=
0
∑
α
r
(
e
1
+
e
2
+
⋯
+
e
r
)
=∏
i
=
1
r
1
2
α
i
(
α
1
+
1
)
⋯
(
α
r
+
1
)
=
1
2
Ω
(
n
)
τ
(
n
)
=\prod_{i=1}^{r}\frac{1}{2}\alpha_i(\alpha_1+1)\cdots (\alpha_r+1)= \frac{1}{2}\Omega(n)\tau(n)
=
i
=
1
∏
r
2
1
α
i
(
α
1
+
1
)
⋯
(
α
r
+
1
)
=
2
1
Ω
(
n
)
τ
(
n
)
解2：
F(
n
)
=
∑
e
1
=
0
α
1
⋯
∑
e
r
=
0
α
r
Ω
(
p
1
e
1
⋯
p
r
e
r
)
F(n) =\sum_{e_1=0}^{\alpha_1} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_1^{e_1} \cdots p_r^{e_r})
F
(
n
)
=
e
1
=
0
∑
α
1
⋯
e
r
=
0
∑
α
r
Ω
(
p
1
e
1
⋯
p
r
e
r
)
=∑
e
2
=
0
α
2
⋯
∑
e
r
=
0
α
r
Ω
(
1
⋅
p
2
e
2
⋯
p
r
e
r
)
+
∑
e
2
=
0
α
2
⋯
∑
e
r
=
0
α
r
Ω
(
p
1
⋅
p
2
e
2
⋯
p
r
e
r
)
+
⋯
+
∑
e
2
=
0
α
2
⋯
∑
e
r
=
0
α
r
Ω
(
p
1
α
1
⋅
p
2
e
2
⋯
p
r
e
r
)
=\sum_{e_2=0}^{\alpha_2} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(1\cdot p_2^{e_2} \cdots p_r^{e_r}) + \sum_{e_2=0}^{\alpha_2} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_1\cdot p_2^{e_2} \cdots p_r^{e_r}) + \cdots +\sum_{e_2=0}^{\alpha_2} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_1^{\alpha_1}\cdot p_2^{e_2} \cdots p_r^{e_r})
=
e
2
=
0
∑
α
2
⋯
e
r
=
0
∑
α
r
Ω
(
1
⋅
p
2
e
2
⋯
p
r
e
r
)
+
e
2
=
0
∑
α
2
⋯
e
r
=
0
∑
α
r
Ω
(
p
1
⋅
p
2
e
2
⋯
p
r
e
r
)
+
⋯
+
e
2
=
0
∑
α
2
⋯
e
r
=
0
∑
α
r
Ω
(
p
1
α
1
⋅
p
2
e
2
⋯
p
r
e
r
)
=(
0
+
1
+
⋯
+
α
1
)
⋅
τ
(
p
2
e
2
⋯
p
r
e
r
)
+
(
1
+
α
1
)
⋅
∑
e
2
=
0
α
2
⋯
∑
e
r
=
0
α
r
Ω
(
p
2
e
2
⋯
p
r
e
r
)
=(0+1+\cdots + \alpha_1)\cdot \tau(p_2^{e_2} \cdots p_r^{e_r}) +(1+\alpha_1)\cdot \sum_{e_2=0}^{\alpha_2} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_2^{e_2} \cdots p_r^{e_r})
=
(
0
+
1
+
⋯
+
α
1
)
⋅
τ
(
p
2
e
2
⋯
p
r
e
r
)
+
(
1
+
α
1
)
⋅
e
2
=
0
∑
α
2
⋯
e
r
=
0
∑
α
r
Ω
(
p
2
e
2
⋯
p
r
e
r
)
=α
1
2
⋅
(
1
+
α
1
)
⋅
τ
(
p
2
e
2
⋯
p
r
e
r
)
+
(
1
+
α
1
)
⋅
∑
e
2
=
0
α
2
⋯
∑
e
r
=
0
α
r
Ω
(
p
2
e
2
⋯
p
r
e
r
)
=\frac{\alpha_1}{2} \cdot (1+\alpha_1)\cdot \tau(p_2^{e_2} \cdots p_r^{e_r}) +(1+\alpha_1)\cdot \sum_{e_2=0}^{\alpha_2} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_2^{e_2} \cdots p_r^{e_r})
=
2
α
1
⋅
(
1
+
α
1
)
⋅
τ
(
p
2
e
2
⋯
p
r
e
r
)
+
(
1
+
α
1
)
⋅
e
2
=
0
∑
α
2
⋯
e
r
=
0
∑
α
r
Ω
(
p
2
e
2
⋯
p
r
e
r
)
=α
1
2
⋅
τ
(
n
)
+
(
1
+
α
1
)
⋅
∑
e
2
=
0
α
2
⋯
∑
e
r
=
0
α
r
Ω
(
p
2
e
2
⋯
p
r
e
r
)
=
1
2
Ω
(
n
)
τ
(
n
)
=\frac{\alpha_1}{2} \cdot \tau(n) +(1+\alpha_1)\cdot \sum_{e_2=0}^{\alpha_2} \cdots \sum_{e_r=0}^{\alpha_r}\Omega(p_2^{e_2} \cdots p_r^{e_r}) =\frac{1}{2}\Omega(n)\tau(n)
=
2
α
1
⋅
τ
(
n
)
+
(
1
+
α
1
)
⋅
e
2
=
0
∑
α
2
⋯
e
r
=
0
∑
α
r
Ω
(
p
2
e
2
⋯
p
r
e
r
)
=
2
1
Ω
(
n
)
τ
(
n
)
-
不同的素因数个数函数，非积性函数
-
例3：求
φ(
n
)
\varphi(n)
φ
(
n
)
的Möbius变换
F(
n
)
F(n)
F
(
n
)
解
：
F(
n
)
=
∑
d
∣
n
φ
(
d
)
=
∏
i
=
1
r
(
1
+
φ
(
p
i
)
+
⋯
+
φ
(
p
i
α
i
)
)
=
∏
i
=
1
r
(
1
+
p
i
−
1
+
p
i
2
−
p
i
+
⋯
+
p
i
α
i
−
p
i
α
i
−
1
)
=
∏
i
=
1
r
p
i
α
i
=
n
F(n)=\sum_{d|n}\varphi(d)=\prod_{i=1}^r(1+\varphi(p_i)+\cdots +\varphi(p_i^{\alpha_i}))\\ =\prod_{i=1}^r(1+p_i-1+p_i^2-p_i+\cdots + p_i^{\alpha_i}-p_i^{\alpha_i-1})\\ =\prod_{i=1}^rp_i^{\alpha_i}=n
F
(
n
)
=
d
∣
n
∑
φ
(
d
)
=
i
=
1
∏
r
(
1
+
φ
(
p
i
)
+
⋯
+
φ
(
p
i
α
i
)
)
=
i
=
1
∏
r
(
1
+
p
i
−
1
+
p
i
2
−
p
i
+
⋯
+
p
i
α
i
−
p
i
α
i
−
1
)
=
i
=
1
∏
r
p
i
α
i
=
n
推论1
设
f
(
n
)
f(n)
f
(
n
)
是积性函数，则
∑
d
∣
n
μ
(
d
)
f
(
d
)
=
∏
p
∣
n
(
1
−
f
(
p
)
)
\sum_{d|n}\mu(d)f(d)=\prod_{p|n}(1-f(p))
d
∣
n
∑
μ
(
d
)
f
(
d
)
=
p
∣
n
∏
(
1
−
f
(
p
)
)
∑
d
∣
n
μ
2
(
d
)
f
(
d
)
=
∏
p
∣
n
(
1
+
f
(
p
)
)
\sum_{d|n}\mu^2(d)f(d)=\prod_{p|n}(1+f(p))
d
∣
n
∑
μ
2
(
d
)
f
(
d
)
=
p
∣
n
∏
(
1
+
f
(
p
)
)
证明
根据定理1（2）可得，
F
(
n
)
=
∑
d
∣
n
μ
(
d
)
f
(
d
)
=
∏
i
=
1
r
(
μ
(
1
)
+
μ
(
p
i
)
⋅
f
(
p
i
)
+
⋯
+
μ
(
p
i
α
i
)
⋅
f
(
p
i
α
i
)
)
F(n)=\sum_{d|n}\mu(d)f(d)= \prod_{i=1}^{r}(\mu(1)+\mu(p_i)\cdot f(p_i)+\cdots +\mu(p_i^{\alpha_i})\cdot f(p_i^{\alpha_i}))
F
(
n
)
=
d
∣
n
∑
μ
(
d
)
f
(
d
)
=
i
=
1
∏
r
(
μ
(
1
)
+
μ
(
p
i
)
⋅
f
(
p
i
)
+
⋯
+
μ
(
p
i
α
i
)
⋅
f
(
p
i
α
i
)
)
=
∏
i
=
1
r
(
1
−
f
(
p
i
)
)
= \prod_{i=1}^{r}(1-f(p_i))
=
i
=
1
∏
r
(
1
−
f
(
p
i
)
)
同理可得：
F
(
n
)
=
∑
d
∣
n
μ
(
d
)
f
(
d
)
=
∏
i
=
1
r
(
μ
2
(
1
)
+
μ
2
(
p
i
)
⋅
f
(
p
i
)
+
⋯
+
μ
2
(
p
i
α
i
)
⋅
f
(
p
i
α
i
)
)
F(n)=\sum_{d|n}\mu(d)f(d)= \prod_{i=1}^{r}(\mu^2(1)+\mu^2(p_i)\cdot f(p_i)+\cdots +\mu^2(p_i^{\alpha_i})\cdot f(p_i^{\alpha_i}))
F
(
n
)
=
d
∣
n
∑
μ
(
d
)
f
(
d
)
=
i
=
1
∏
r
(
μ
2
(
1
)
+
μ
2
(
p
i
)
⋅
f
(
p
i
)
+
⋯
+
μ
2
(
p
i
α
i
)
⋅
f
(
p
i
α
i
)
)
=
∏
i
=
1
r
(
1
+
f
(
p
i
)
)
= \prod_{i=1}^{r}(1+f(p_i))
=
i
=
1
∏
r
(
1
+
f
(
p
i
)
)
例题
-
f(
n
)
=
1
f(n)=1
f
(
n
)
=
1
，则
∑d
∣
n
μ
(
d
)
⋅
1
=
I
(
n
)
\sum_{d|n}\mu(d)\cdot 1=I(n)
∑
d
∣
n
μ
(
d
)
⋅
1
=
I
(
n
)
-
f(
n
)
=
1
/
n
f(n)=1/n
f
(
n
)
=
1
/
n
，则
∑d
∣
n
μ
(
d
)
/
d
=
φ
(
n
)
/
n
\sum_{d|n}\mu(d)/d=\varphi(n)/n
∑
d
∣
n
μ
(
d
)
/
d
=
φ
(
n
)
/
n
定理3
设
f
(
n
)
、
F
(
n
)
f(n)、F(n)
f
(
n
)
、
F
(
n
)
是数论函数，那么
F
(
n
)
=
∑
d
∣
n
f
(
d
)
=
∑
d
∣
n
f
(
n
d
)
⇔
f
(
n
)
=
∑
d
∣
n
μ
(
d
)
F
(
n
d
)
=
∑
d
∣
n
μ
(
n
d
)
F
(
d
)
F(n)=\sum_{d|n}f(d)=\sum_{d|n}f(\frac{n}{d}) \quad \Leftrightarrow \quad f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})F(d)
F
(
n
)
=
d
∣
n
∑
f
(
d
)
=
d
∣
n
∑
f
(
d
n
)
⇔
f
(
n
)
=
d
∣
n
∑
μ
(
d
)
F
(
d
n
)
=
d
∣
n
∑
μ
(
d
n
)
F
(
d
)
证明
关键
：“关联约束”
→
转化
\overset{\text{转化}}{\rightarrow}
→
转化
“独立约束”
∑
d
∣
n
g
(
n
d
)
∑
k
∣
d
f
(
k
)
=
k
⋅
l
=
d
∑
k
⋅
l
∣
n
g
(
n
k
⋅
l
)
f
(
k
)
=
∑
k
∣
n
f
(
k
)
∑
l
∣
n
k
g
(
l
)
\sum_{d|n}g(\frac{n}{d})\sum_{k|d}f(k) \overset{k\cdot l=d}{=} \sum_{k\cdot l|n}g(\frac{n}{k\cdot l})f(k)=\sum_{k|n}f(k)\sum_{l|\frac{n}{k}}g(l)
d
∣
n
∑
g
(
d
n
)
k
∣
d
∑
f
(
k
)
=
k
⋅
l
=
d
k
⋅
l
∣
n
∑
g
(
k
⋅
l
n
)
f
(
k
)
=
k
∣
n
∑
f
(
k
)
l
∣
k
n
∑
g
(
l
)
∑
d
∣
n
∑
k
∣
d
g
(
d
k
)
f
(
k
)
=
d
⋅
l
=
n
∑
k
⋅
l
∣
n
g
(
n
k
⋅
l
)
f
(
k
)
=
∑
k
∣
n
f
(
k
)
∑
l
∣
n
k
g
(
l
)
\sum_{d|n}\sum_{k|d}g(\frac{d}{k})f(k) \overset{d\cdot l=n}{=} \sum_{k\cdot l|n}g(\frac{n}{k\cdot l})f(k)=\sum_{k|n}f(k)\sum_{l|\frac{n}{k}}g(l)
d
∣
n
∑
k
∣
d
∑
g
(
k
d
)
f
(
k
)
=
d
⋅
l
=
n
k
⋅
l
∣
n
∑
g
(
k
⋅
l
n
)
f
(
k
)
=
k
∣
n
∑
f
(
k
)
l
∣
k
n
∑
g
(
l
)
-
充分性
∑d
∣
n
f
(
d
)
=
∑
d
∣
n
{
∑
k
∣
d
μ
(
d
k
)
F
(
k
)
}
=
∑
k
∣
n
F
(
k
)
∑
l
∣
n
k
μ
(
l
)
=
F
(
n
)
\sum_{d|n}f(d)=\sum_{d|n}\left\{\sum_{k|d}\mu(\frac{d}{k})F(k)\right\}=\sum_{k|n}F(k)\sum_{l|\frac{n}{k}}\mu(l)=F(n)
d
∣
n
∑
f
(
d
)
=
d
∣
n
∑
⎩
⎨
⎧
k
∣
d
∑
μ
(
k
d
)
F
(
k
)
⎭
⎬
⎫
=
k
∣
n
∑
F
(
k
)
l
∣
k
n
∑
μ
(
l
)
=
F
(
n
)
-
必要性
∑d
∣
n
μ
(
n
d
)
F
(
d
)
=
∑
d
∣
n
μ
(
n
d
)
∑
k
∣
d
f
(
k
)
=
∑
k
∣
n
f
(
k
)
∑
l
∣
n
k
μ
(
l
)
=
f
(
n
)
\sum_{d|n}\mu(\frac{n}{d})F(d)=\sum_{d|n}\mu(\frac{n}{d})\sum_{k|d}f(k) =\sum_{k|n}f(k)\sum_{l|\frac{n}{k}}\mu(l)=f(n)
d
∣
n
∑
μ
(
d
n
)
F
(
d
)
=
d
∣
n
∑
μ
(
d
n
)
k
∣
d
∑
f
(
k
)
=
k
∣
n
∑
f
(
k
)
l
∣
k
n
∑
μ
(
l
)
=
f
(
n
)
例题
1
=
∑
d
∣
n
μ
(
d
)
τ
(
n
d
)
=
∑
d
∣
n
μ
(
n
d
)
τ
(
d
)
1=\sum_{d|n}\mu(d)\tau(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})\tau(d)
1
=
d
∣
n
∑
μ
(
d
)
τ
(
d
n
)
=
d
∣
n
∑
μ
(
d
n
)
τ
(
d
)
n
=
∑
d
∣
n
μ
(
d
)
σ
(
n
d
)
=
∑
d
∣
n
μ
(
n
d
)
σ
(
d
)
n=\sum_{d|n}\mu(d)\sigma(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})\sigma(d)
n
=
d
∣
n
∑
μ
(
d
)
σ
(
d
n
)
=
d
∣
n
∑
μ
(
d
n
)
σ
(
d
)
φ
(
n
)
=
∑
d
∣
n
μ
(
d
)
(
n
d
)
=
∑
d
∣
n
μ
(
n
d
)
d
\varphi(n)=\sum_{d|n}\mu(d)(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})d
φ
(
n
)
=
d
∣
n
∑
μ
(
d
)
(
d
n
)
=
d
∣
n
∑
μ
(
d
n
)
d
μ
(
n
)
n
=
∑
d
∣
n
μ
(
d
)
φ
(
n
d
)
/
n
d
=
∑
d
∣
n
μ
(
n
/
d
[
]
)
φ
(
d
)
d
\frac{\mu(n)}{n}=\sum_{d|n}\mu(d)\varphi(\frac{n}{d})/\frac{n}{d}=\sum_{d|n}\frac{\mu(n/d[])\varphi(d)}{d}
n
μ
(
n
)
=
d
∣
n
∑
μ
(
d
)
φ
(
d
n
)
/
d
n
=
d
∣
n
∑
d
μ
(
n
/
d
[
]
)
φ
(
d
)
定理4
设
f
(
n
)
、
g
(
n
)
f(n)、g(n)
f
(
n
)
、
g
(
n
)
是数论函数，
h
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
n
d
)
h(n)=\sum_{d|n}f(d)g(\frac{n}{d})
h
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
d
n
)
，那么，当
f
(
n
)
、
g
(
n
)
f(n)、g(n)
f
(
n
)
、
g
(
n
)
都是积性函数时，
h
(
n
)
h(n)
h
(
n
)
也是积性函数.
证明
-
f(
1
)
=
g
(
1
)
=
1
→
h
(
1
)
=
1
f(1)=g(1)=1 \rightarrow h(1)=1
f
(
1
)
=
g
(
1
)
=
1
→
h
(
1
)
=
1
-
若
(m
，
n
)
=
1
(m，n)=1
(
m
，
n
)
=
1
h(
m
n
)
=
∑
d
∣
m
n
f
(
m
n
)
g
(
m
n
d
)
=
∑
d
1
d
2
∣
m
n
f
(
m
n
)
g
(
m
n
d
1
d
2
)
=
∑
d
1
∣
m
f
(
m
)
g
(
m
d
1
)
⋅
∑
d
2
∣
n
f
(
n
)
g
(
n
d
2
)
=
h
(
m
)
h
(
n
)
h(mn)=\sum_{d|mn}f(mn)g(\frac{mn}{d})=\sum_{d_1d_2|mn}f(mn)g(\frac{mn}{d_1d_2})=\sum_{d_1|m}f(m)g(\frac{m}{d_1})\cdot \sum_{d_2|n}f(n)g(\frac{n}{d_2})=h(m)h(n)
h
(
m
n
)
=
d
∣
m
n
∑
f
(
m
n
)
g
(
d
m
n
)
=
d
1
d
2
∣
m
n
∑
f
(
m
n
)
g
(
d
1
d
2
m
n
)
=
d
1
∣
m
∑
f
(
m
)
g
(
d
1
m
)
⋅
d
2
∣
n
∑
f
(
n
)
g
(
d
2
n
)
=
h
(
m
)
h
(
n
)
说明
：
- m、n互质，它们的素因子互不相同；
-
d的素因子要么来自m，要么来自n，所以d可以分解成
d1
、
d
2
d_1、d_2
d
1
、
d
2
，它们的素因子分别来自m和n； -
关联约束
→转化
\overset{\text{转化}}{\rightarrow}
→
转化
独立约束。
推论2
f
(
n
)
f(n)
f
(
n
)
是积性函数的充分必要条件是它的Möbius变换
F
(
n
)
F(n)
F
(
n
)
是积性函数.
证明
∵
μ
(
n
)
、
F
(
n
)
\because \mu(n)、F(n)
∵
μ
(
n
)
、
F
(
n
)
是积性函数
∴
\therefore
∴
根据定理4可得，
f
(
n
)
=
∑
d
∣
n
μ
(
n
d
)
F
(
d
)
是
积
性
函
数
f(n)=\sum_{d|n}\mu(\frac{n}{d})F(d) 是积性函数
f
(
n
)
=
∑
d
∣
n
μ
(
d
n
)
F
(
d
)
是
积
性
函
数
.
例题
提示
：求解积性函数F(n)的Möbius逆变换f(n)时，根据
f
(
p
α
)
=
F
(
p
α
)
−
F
(
p
α
−
1
)
f(p^\alpha)=F(p^\alpha)-F(p^{\alpha-1})
f
(
p
α
)
=
F
(
p
α
)
−
F
(
p
α
−
1
)
计算.
-
例1：求
F(
n
)
=
n
t
F(n)=n^t
F
(
n
)
=
n
t
的Möbius逆变换.
解
：
∵F
(
n
)
=
n
t
是
积
性
函
数
\because F(n)=n^t 是积性函数
∵
F
(
n
)
=
n
t
是
积
性
函
数
∴f
(
p
α
)
=
F
(
p
α
)
−
F
(
p
α
−
1
)
=
(
p
α
)
t
−
(
p
α
−
1
)
t
=
p
α
t
(
1
−
p
−
t
)
\therefore f(p^\alpha)=F(p^\alpha)-F(p^{\alpha-1})=(p^\alpha)^t-(p^{\alpha-1})^t =p^{\alpha t}(1-p^{-t})
∴
f
(
p
α
)
=
F
(
p
α
)
−
F
(
p
α
−
1
)
=
(
p
α
)
t
−
(
p
α
−
1
)
t
=
p
α
t
(
1
−
p
−
t
)
∴f
(
n
)
=
n
t
⋅
∏
p
∣
n
(
1
−
p
−
t
)
\therefore f(n)=n^t\cdot \prod_{p|n}(1-p^{-t})
∴
f
(
n
)
=
n
t
⋅
p
∣
n
∏
(
1
−
p
−
t
)
-
例2：求
F(
n
)
=
φ
(
n
)
F(n)=\varphi(n)
F
(
n
)
=
φ
(
n
)
的Möbius逆变换.
解
：
∵F
(
n
)
=
φ
(
n
)
是
积
性
函
数
\because F(n)=\varphi(n) 是积性函数
∵
F
(
n
)
=
φ
(
n
)
是
积
性
函
数
∴f
(
p
α
)
=
φ
(
p
α
)
−
φ
(
p
α
−
1
)
=
{
p
(
1
−
2
p
)
α
=
1
p
α
(
1
−
1
p
)
2
α
≥
2
\therefore f(p^\alpha)=\varphi(p^\alpha)-\varphi(p^{\alpha-1})= \begin{cases} p(1-\frac{2}{p}) & \alpha=1\\ p^\alpha(1-\frac{1}{p})^2 & \alpha \geq2 \end{cases}
∴
f
(
p
α
)
=
φ
(
p
α
)
−
φ
(
p
α
−
1
)
=
{
p
(
1
−
p
2
)
p
α
(
1
−
p
1
)
2
α
=
1
α
≥
2
∴f
(
n
)
=
n
⋅
∏
p
∣
∣
n
(
1
−
2
p
)
∏
p
2
∣
n
(
1
−
1
p
)
2
\therefore f(n)=n\cdot \prod_{p||n}(1-\frac{2}{p})\prod_{p^2|n}(1-\frac{1}{p})^2
∴
f
(
n
)
=
n
⋅
p
∣
∣
n
∏
(
1
−
p
2
)
p
2
∣
n
∏
(
1
−
p
1
)
2
说明
：符号
ak
∣
∣
b
a^k||b
a
k
∣
∣
b
表示 b 恰好被
ak
a^k
a
k
整除.
3 Dirichlet卷积
定义
设
h
(
n
)
=
∑
d
∣
n
f
(
n
)
g
(
n
d
)
h(n)=\sum_{d|n}f(n)g(\frac{n}{d})
h
(
n
)
=
∑
d
∣
n
f
(
n
)
g
(
d
n
)
是定义在数论函数集合上的一种运算，则称
h
(
n
)
h(n)
h
(
n
)
是
f
(
n
)
、
g
(
n
)
f(n)、g(n)
f
(
n
)
、
g
(
n
)
的Dirichlet卷积，记作
h
=
f
∗
g
h=f * g
h
=
f
∗
g
，且有
h
(
n
)
=
(
f
∗
g
)
(
n
)
h(n)=(f*g)(n)
h
(
n
)
=
(
f
∗
g
)
(
n
)
，
f
∗
g
f * g
f
∗
g
可以看作一个算子.
性质
-
h(
n
)
=
(
f
∗
g
)
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
n
d
)
=
∑
d
∣
n
f
(
n
d
)
g
(
d
)
=
∑
d
⋅
l
=
n
f
(
d
)
g
(
l
)
h(n)=(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)=\sum_{d\cdot l=n}f(d)g(l)
h
(
n
)
=
(
f
∗
g
)
(
n
)
=
∑
d
∣
n
f
(
d
)
g
(
d
n
)
=
∑
d
∣
n
f
(
d
n
)
g
(
d
)
=
∑
d
⋅
l
=
n
f
(
d
)
g
(
l
)
-
g∗
f
=
f
∗
g
g * f =f * g
g
∗
f
=
f
∗
g
-
g∗
(
f
∗
k
)
=
(
g
∗
f
)
∗
k
g * (f * k) =(g * f)* k
g
∗
(
f
∗
k
)
=
(
g
∗
f
)
∗
k