「Learning Notes」Arithmetic Functions

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Notations

若无特殊说明,下文中出现的所有 p 均为质数。

下文中出现的 '\ast' 符号,若无特殊说明,均表示狄利克雷卷积 ( Dirichlet Convolution ) .

Definitions

f(n) 的定义域为 \mathbb{Z^{+}} ,值域为 \mathbb{C} ,即:

f:\mathbb{Z^{+}}\to\mathbb{C}

则称 f(n) 数论函数 ( Arithmetic Function ) .

f(n) 为数论函数,且

f(1)=1

\forall a,b\in\mathbb{Z^{+}},\left(a,b\right)=1:f\left(ab\right)=f\left(a\right)+f\left(b\right)

则称 f(n) 加性函数 ( Additive Function ) .

f(n) 为数论函数,且

f(1)=1

\forall a,b\in\mathbb{Z^{+}}:f\left(ab\right)=f\left(a\right)+f\left(b\right)

则称 f(n) 完全加性函数 ( Completely Additive Function ) .

f(n) 为数论函数,且

f(1)=1

\forall a,b\in\mathbb{Z^{+}},\left(a,b\right)=1:f\left(ab\right)=f\left(a\right)f\left(b\right)

则称 f(n) 积性函数 ( Multiplicative Function ) .

f(n) 为数论函数,且

f(1)=1

\forall a,b\in\mathbb{Z^{+}}:f\left(ab\right)=f\left(a\right)f\left(b\right)

则称 f(n) 完全积性函数 ( Completely Multiplicative Function ) .

狄利克雷卷积 ( Dirichlet Convolution ) 定义在数论函数上,记号为 '\ast'

(f \ast g)(n)=\sum_{d | n}f(d)g\left(\frac{n}{d}\right)=\sum_{ab=n}f\left(a\right)g\left(b\right)

Arithmetic Functions

此处仅介绍部分常见的数论函数的定义.

Additive Functions

1. Prime Omega Function: \omega(n)

\omega(n)=\sum_{p}\left[p | n\right]

亦即数 n 不同的质因数个数。

Completely Additive Functions

1. p-adic order: \nu_{p}(n)

\nu_{p}(n)=\left\{\begin{matrix}\infty&n=0\\max\left\{v\in\mathbb{N}:p^{v} | n\right\}&n\ne 0\end{matrix}\right.

亦即 n 标准分解式 p 的指数。

2. Prime Omega Function: \Omega(n)

\Omega(n)=\sum_{p}\nu_{p}(n)

亦即数 n 的质因数个数。

Multiplicative Functions

1. Möbius Function: \mu(n) :

\mu(n)=\delta_{\omega(n)\Omega(n)}\lambda(n)

其中 \delta Kronecker Delta:

\delta_{ij}=[i=j]

\lambda(n) 为 Liouillve Function.
亦有:

\mu(n)=\begin{cases}0&\omega(n)\ne\Omega(n)\\(-1)^{\omega(n)}&\omega(n)=\Omega(n)\end{cases}

2. Euler's Totient Function: \varphi(n)

\varphi(n)=\sum_{k=1}^{n}\left[\left(k,n\right)=1\right]

亦即在 [1, n] 中与 n 互质的数的个数。

3. Jordan's Totient Function: J_{k}(n)

J_{k}(n)=\sum_{c_{1}=1}^{n}\sum_{c_{2}=1}^{n}...\sum_{c_{k}=1}^{n}\left[\left(\gcd_{i=1}^{k}c_{i},n\right)=1\right]

亦即从 [1, n] 中选出 k 个数 \left\{c_{k}\right\} 使得 \left(\gcd_{i=1}^{k}c_{i},n\right)=1 的方案数。
k=1 时即为 Euler's Totient Function.

J_{1}(n)=\varphi(n)

4. Divisor Function: \sigma_{k}(n),\sigma(n),\tau(n),d(n)

\sigma_{k}(n)=\sum_{d | n}d^{k}

亦即 n 所有因数的 k 次方和。

\sigma_{1}(n) 也记作 \sigma(n)

\sigma(n)=\sigma_{1}(n)=\sum_{d | n}d

亦即 n 所有因数之和。

\sigma_{0}(n) 也记作 \tau(n) d(n)

\tau(n)=d(n)=\sigma_{0}(n)

亦即 n 的因数个数。

Completely Multiplicative Functions

1. Unit Function: \epsilon(n)

\epsilon(n)=\left[n=1\right]

亦即 \epsilon(n) 1 当且仅当 n=1
\epsilon 为 Dirichlet Convolution 下的单位元:

\left(f\ast\epsilon\right)=f

2. Identity Function: I(n),I_{k}(n)

I(n)=n

I_{k}(n)=n^{k}

也记作 Id(n) Id_{k}(n)

3. Constant Function: 1(n)

1(n)=1

Constant Function 不仅限于 1(n) ,但通常使用的都是 1(n)=1

4. Liouville Function: \lambda(n)

\lambda(n)=(-1)^{\Omega(n)}

Properties

此处只简要讲一些相对重要的性质|公式及证明.

1. Dirichlet Convolution

1.1. Dirichlet Convolution 满足交换律:

f\ast g=g\ast f

证明:
易知对于每个 d | n 均有唯一一个 \displaystyle\frac{n}{d} 与之对应

(f \ast g)(n)=\sum_{d | n}f(d)g\left(\frac{n}{d}\right)=\sum_{d | n}f\left(\frac{n}{d}\right)g(d)=\left(g\ast f\right)(n)

f\ast g=g\ast f

证毕.

1.2. Dirichlet Convolution 满足分配律:

f\ast\left(g+h\right)=f\ast g+f\ast h

证明:

\begin{aligned} \left(f\ast\left(g+h\right)\right)(n)=&\sum_{d | n}f(d)\left(g\left(\frac{n}{d}\right)+h\left(\frac{n}{d}\right)\right)\\ =&\sum_{d | n}f(d)g\left(\frac{n}{d}\right)+\sum_{d | n}f(d)h\left(\frac{n}{d}\right)\\ =&\left(f\ast g+f\ast h\right)(n) \end{aligned}

f\ast\left(g+h\right)=f\ast g+f\ast h

证毕.

1.3. Dirichlet Convolution 满足结合律:

(f \ast g)\ast h=f\ast\left(g\ast h\right)

证明:

\left((f \ast g)\ast h\right)(n)=\sum_{d | n}\sum_{e | d}f(e)g\left(\frac{d}{e}\right)h\left(\frac{n}{d}\right)

\left(f\ast\left(g\ast h\right)\right)(n)=\sum_{d | n}\sum_{e | d}f\left(\frac{n}{d}\right)g(e)h\left(\frac{d}{e}\right)

d'=\frac{n}{e},e'=\frac{d}{e}

则易知对于 \left((f \ast g)\ast h\right)(n) 中的每一项 \displaystyle{f(e)g\left(\frac{d}{e}\right)h\left(\frac{n}{d}\right)}
都能在 \left(f\ast\left(g\ast h\right)\right)(n) 中找到与其相等的一项 \displaystyle{f\left(\frac{n}{d'}\right)g\left(e'\right)h\left(\frac{d'}{e'}\right)} 与之对应.

\sum_{d | n}\sum_{e | d}f(e)g\left(\frac{d}{e}\right)h\left(\frac{n}{d}\right)=\sum_{d | n}\sum_{e | d}f\left(\frac{n}{d}\right)g(e)h\left(\frac{d}{e}\right)

\left((f \ast g)\ast h\right)(n)=\left(f\ast\left(g\ast h\right)\right)(n)

(f \ast g)\ast h=f\ast\left(g\ast h\right)

证毕.

1.4. 在 Dirichlet Convolution 下存在单位元 \epsilon

f\ast\epsilon=\epsilon\ast f=f

此即 Unit Function.
证明:

\left(f\ast\epsilon\right)(n)=\sum_{d | n}f(d)\epsilon\left(\frac{n}{d}\right)

由 Unit Function 的定义可知
当且仅当 \frac{n}{d}=1 \epsilon\left(\frac{n}{d}\right)=1
此时 d=n ,故只有 d=n 的一项对答案有贡献:

\left(f\ast\epsilon\right)(n)=f(n)\epsilon(1)=f(n)

证毕.

1.5. Dirichlet Convolution 具有封闭性:
设数论函数集为 \mathbb{I}

\forall f,g\in\mathbb{I}:f\ast g\in\mathbb{I}

证明:
f\ast g 的每一项均为 f g 的点值之积,故 f\ast g 的每一项均在 \mathbb{C} 内,即 f\ast g 的值域为 \mathbb{C}
证毕.

1.6. 两个积性函数的 Dirichlet Convolution 仍是积性函数。
证明:

h=f\ast g

其中 f,g 为积性函数,则:

\begin{aligned} h\left(a\right)h\left(b\right)=&\sum_{d_{a} | a}f\left(d_{a}\right)g\left(\frac{a}{d_{a}}\right)\sum_{d_{b} | b}f\left(d_{b}\right)g\left(\frac{b}{d_{b}}\right)\\ =&\sum_{d_{a} | a}\sum_{d_{b} | b}f\left(d_{a}\right)g\left(\frac{a}{d_{a}}\right)f\left(d_{b}\right)g\left(\frac{b}{d_{b}}\right) \end{aligned}

由于 \left(a,b\right)=1 ,故

\forall d_{a} | a,d_{b} | b:\left(d_{a},d_{b}\right)=1

f,g 均为积性函数,故

h\left(a\right)h\left(b\right)=\sum_{d_{a} | a,d_{b} | b}f\left(d_{a}d_{b}\right)g\left(\frac{ab}{d_{a}d_{b}}\right)=h\left(ab\right)

证毕.

1.7. Dirichlet Convolution on common Arithmetic Functions:

\mu\ast 1=\epsilon

g=f\ast 1\Leftrightarrow f=g\ast\mu

\varphi\ast 1=I

J_{k}\ast 1=I_{k}

\sigma_{k}=I_{k}\ast 1\Leftrightarrow I_{k}=\sigma_{k}\ast\mu

\sigma=I\ast 1\Leftrightarrow I=\sigma\ast\mu

d=1\ast 1\Leftrightarrow 1=d\ast\mu

\sigma=\varphi\ast d

证明见下.

2. \mu(n) 1(n) 在 Dirichlet Convolution 下互为逆元:

\mu\ast 1=\epsilon

亦即

\sum_{d | n}\mu(d)=\left[n=1\right]

证明:
n=1 时,有

\sum_{d | n}\mu(d)=\mu(1)=1

n\ne 1 时,由 \mu(n) 的定义可以发现当 d 含有一个以上的质因子时对答案无贡献,即 \mu(n)=0
故只需考虑从 r n 的质因子中选出 k 个的方案数:

\sum_{d | n}\mu(d)=\sum_{k=0}^{r}\binom{r}{k}(-1)^{k}=\left(1-1\right)^{r}=0

证毕.
由此可得 Möbius Inversion Formula 的标准形式:

g(n)=\sum_{d | n}f(n)\Leftrightarrow g=1\ast f\Leftrightarrow\mu\ast g=\mu\ast 1\ast f=\epsilon\ast f=f\Leftrightarrow f(n)=\sum_{d | n}\mu(d)g\left(\frac{n}{d}\right)

3. \varphi(n) 的求值公式:

\varphi(n)=n\prod_{i=1}^{\omega(n)}\left(1-\frac{1}{p_{i}}\right)

推导分两步:

3.1. 证明 \varphi(n) 为积性函数,即:

\forall n,m\in\mathbb{Z^{+}},\left(n,m\right)=1:\varphi\left(nm\right)=\varphi(n)\varphi\left(m\right)

易知 \left(x,nm\right)=1,\left(n,m\right)=1 等价于 \left(x,n\right)=1,\left(x,m\right)=1
考虑构造一个 n\times m 的矩阵 A 使其满足

A_{r,c}=\left(r-1\right)m+c

A=\begin{bmatrix}1&2&...&c&...&m\\m+1&m+2&...&m+c&...&2m\\...&...&...&...&...&...\\\left(r-1\right)m+1&\left(r-1\right)m+2&...&\left(r-1\right)m+c&...&rm\\...&...&...&...&...&...\\(n - 1)m+1&(n - 1)m+2&...&(n - 1)m+c&...&nm\end{bmatrix}

易知

\left(rm+c,m\right)=\left(c,m\right)

故第 c 列的所有元素同时与 m 互质当且仅当 \left(c,m\right)=1
\varphi(n) 的定义可知共有 \varphi\left(m\right) 列的元素与 m 互质,考虑这 m 列的元素可以发现第 c 列的 n 个元素

c,m+c,2m+c,...,\left(r-1\right)m+c,(n - 1)m+c

正好构成了 n 意义下的完全剩余系 ( Complete Residue System Modulo n ) .
\varphi\left(m\right) 列中的每一列都恰有 \varphi(n) 个与 n 互质的数。

\varphi\left(nm\right)=\varphi(n)\varphi\left(m\right)

证毕.

3.2. 求出对于任意 k\in\mathbb{Z^{+}} 的函数值 \varphi\left(p^{k}\right)
由于 p 为质数,故若 \left(x,p^{k}\right)\ne 1 ,则必有 p | x ,则:

p^{k}-\varphi\left(p^{k}\right)=\sum_{x=1}^{p^{k}}\left[p | x\right]=p^{k-1}

\varphi\left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}\left(p-1\right)=p^{k}\left(1-\frac{1}{p}\right)

则对于任意 n\in\mathbb{Z^{+}} ,有:

\begin{aligned} \varphi(n)=&\prod_{i=1}^{\omega(n)}\left(p_{i}^{\nu_{p_{i}}(n)}\left(1-\frac{1}{p_{i}}\right)\right)\\ =&\prod_{i=1}^{\omega(n)}p_{i}^{\nu_{p_{i}}(n)}\times\prod_{i=1}^{\omega(n)}\left(1-\frac{1}{p_{i}}\right)\\ =&n\prod_{i=1}^{\omega(n)}\left(1-\frac{1}{p_{i}}\right) \end{aligned}

4.

\varphi\ast 1=I=Id

亦即

\sum_{d | n}\varphi(d)=n

证明:

f=\varphi\ast 1

则对于任意 k\in\mathbb{Z^{+}} ,有:

f\left(p^{k}\right)=\sum{d | p^{k}}\varphi(d)

又由 p 为质数,故 p^{k} 的因数只可能是 p^{j}\left(0\le j\le k\right) ,则:

\begin{aligned} f\left(p^{k}\right)=&\sum_{j=0}^{k}\varphi\left(p^{j}\right)\\ =&\varphi\left(p^{0}\right)+\sum_{j=1}^{k}p^{j}-p^{j-1}\\ =&p^{k}-p^{k-1}+p^{k-1}+...+p^{1}-p^{0}+1\\ =&p^{k}\\ =&I\left(p^{k}\right) \end{aligned}

即对于所有满足 \omega(n)\le 1 的数都有 f=I 满足.
\varphi,1,I 均为积性函数,故 f=\varphi\ast 1 也为积性函数 ( 性质 1.6 )
则:

f(n)=\prod_{i=1}^{\omega(n)}f\left(p_{i}^{\nu_{p_{i}}(n)}\right)=\prod_{i=1}^{\omega(n)}I\left(p_{i}^{\nu_{p_{i}}(n)}\right)=I(n)

证毕.

5. J_{k}(n) 的求值公式:

J_{k}(n)=n^{k}\prod_{i=1}^{\omega(n)}\left(1-\frac{1}{p_{i}^{k}}\right)

推导:

\begin{aligned} J_{k}(n) &=\sum_{c_{1}=1}^{n}\sum_{c_{2}=1}^{n}...\sum_{c_{k}=1}^{n}\left[\left(\gcd_{i=1}^{k}c_{i},n\right)=1\right]\\ &=\sum_{c_{1}=1}^{n}\sum_{c_{2}=1}^{n}...\sum_{c_{k}=1}^{n}\sum_{d |\left(\gcd_{i=1}^{k}c_{i},n\right)}\mu(d)\\ &=\sum_{d=1}^{n}\mu(d)\left(\sum_{c_{1}=1}^{n}\left[d | c_{1}\right]\right)\left(\sum_{c_{2}=1}^{n}\left[d | c_{2}\right]\right)...\left(\sum_{c_{k}=1}^{n}\left[d | c_{k}\right]\right)\\ &=\sum_{d=1}^{n}\mu(d)\left(\frac{n}{d}\right)^{k} \end{aligned}

可以发现当且仅当 \omega(d)=\Omega(d) \displaystyle\left(\frac{n}{d}\right)^{k} 才有贡献 ( \mu(d)\ne 0 )
考虑枚举 \omega(d) ,则有:

J_{k}(n)=\sum_{r=0}^{\omega(n)}(-1)^{\omega(n)-r}\left(\prod_{i=1}^{\omega(n)}p_{i}^{\nu_{p_{i}}(n)-1}\right)^{k}\sum_{\left\{a_{r}\right\}}\left(\prod_{i=1}^{r}p_{a_{i}}\right)^{k}

其中

1\le a_{1}<a_{2}<...<a_{r-1}<a_{r}\le\omega(n)

因式分解可得

J_{k}(n)=\prod_{i=1}^{\omega(n)}p_{i}^{\nu_{p_{i}}(n)k}\left(1-\frac{1}{p_{i}^{k}}\right)=n^{k}\prod_{i=1}^{\omega(n)}\left(1-\frac{1}{p_{i}^{k}}\right)

6.

J_{k}\ast 1=I_{k}=Id_{k}

亦即

\sum_{d | n}J_{k}(d)=n^{k}

证明:

类似于性质 4 的证明,记

f_{k}=J_{k}\ast 1

则对于任意 k'\in\mathbb{Z^{+}} ,有:

f_{k}\left(p^{k'}\right)=\sum{d | p^{k'}}J_{k}(d)

又由 p 为质数,故 p^{k'} 的因数只可能是 p^{j}\left(0\le j\le k'\right) ,则:

\begin{aligned} f_{k}\left(p^{k'}\right) &=\sum_{j=0}^{k'}J_{k}\left(p^{j}\right)\\ &=J_{k}\left(p^{0}\right)+\sum_{j=1}^{k'}p^{jk}-p^{\left(j-1\right)k}\\ &=p^{k'k}-p^{\left(k'-1\right)k}+p^{\left(k'-1\right)k}-p^{\left(k'-2\right)k}+...+p^{k}-1+1\\ &=p^{k'k}\\ &=I_{k}\left(p^{k'}\right) \end{aligned}

即对于所有满足 \omega(n)\le 1 的数都有 f_{k}=I_{k} 满足.
J_{k},1,I_{k} 均为积性函数,故 f_{k}=J_{k}\ast 1 也为积性函数 ( 性质 1.6 )
则:

f_{k}(n)=\prod_{i=1}^{\omega(n)}f_{k}\left(p_{i}^{\nu_{p_{i}}(n)}\right)=\prod_{i=1}^{\omega(n)}I_{k}\left(p_{i}^{\nu_{p_{i}}(n)}\right)=I_{k}(n)

证毕.

7. \sigma_{k}(n) 的求值公式:

\sigma_{k}(n)=\prod_{i=1}^{\omega(n)}\sum_{j=0}^{\nu_{p_{i}}(n)}p_{i}^{jk}=\prod_{i=1}^{\omega(n)}\frac{p_{i}^{\left(\nu_{p_{i}}(n)+1\right)k}-1}{p_{i}^{k}-1}

证明:

将上式展开可得

\sigma_{k}(n)=\sum_{c\in S}\prod_{i=1}^{\omega(n)}p_{i}^{c_{i}k}=\sum_{c\in S}\left(\prod_{i=1}^{k}p_{i}^{c_{i}}\right)^{k}

其中

S=\left\{c |\forall i\in[1, r]:0\le c_{i}\le a_{i}\right\}