解析数论/数论函数公式

莫比乌斯 μ 函数的公式

引理 2.9:

$\sum _{d|n}\mu (d){\frac {n}{d}}=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)$.

证明:

对于 $\kappa \in \mathbb {Z} ^{r}$ 多重索引， $\alpha \in \{0,1\}^{r}$ 以及 $Q\in \mathbb {C} ^{r}$ 向量定义

$Q^{\alpha }:=\prod _{j=1}^{r}q_{j}^{\alpha _{j}}$,

$Q^{\kappa }:=(q_{1}^{k_{1}},\ldots ,q_{r}^{k_{r}})$.

令 $n=(P^{\kappa })^{1}=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. 然后

${\begin{aligned}\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)&=\sum _{\alpha \in \{0,1\}^{r}}(P^{\kappa })^{\alpha }(P^{\kappa -1})^{1-\alpha }(-1)^{|}{1-\alpha |}\\&=\sum _{d|n}\mu (d){\frac {n}{d}}\end{aligned}}$.$\Box$

引理 2.10:

$\varphi =\mu *I_{1}$.

证明 1:

我们从引理 2.14 中证明这个引理。

根据引理 2.14，我们有

${\begin{aligned}\varphi (n)&=\sum _{k=1}^{n}\delta (\gcd(k,n))\\&=\sum _{k=1}^{n}\sum _{d|\gcd(k,n)}\mu (d)\\&=\sum _{d|n}\sum _{k=1}^{n}[d|k]\mu (d)\\&=\sum _{d|n}\sum _{j=1}^{n/d}\mu (d)\end{aligned}}$$\Box$

证明 2:

我们利用欧拉函数的积公式和引理 2.9 来证明此引理。事实上，对于 $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$

$\varphi (n)=\prod _{j=1}^{r}(p_{j}^{k_{j}}-p_{j}^{k_{j}-1})=\mu *I_{1}$.$\Box$

引理 2.14:

$E*\mu =\delta$.

证明 1:

我们使用莫比乌斯反演公式。

事实上，$E(n)=\sum _{d|n}\delta (d)=1$，因此$\delta =\mu *E$.$\Box$

证明 2:

我们使用乘法性。

事实上，对于素数 $p$，$k\in \mathbb {N}$ 我们有

$E*\mu (p^{k})=\sum _{j=0}^{k}\mu (p^{j})=\mu (1)+\mu (p)=0$,

因此，由于 $\mu$ 和 $E$ 的乘法性，$E*\mu (n)=0$ 当 $n$ 包含至少一个素因子。由于进一步 $E*\mu (1)=1$，结论成立。$\Box$

证明 3:

我们通过直接计算来证明引理。实际上，如果 $1\neq n=P^{\kappa }$，则

${\begin{aligned}E*\mu (n)&=\sum _{d|n}\mu (d)\\&=\sum _{\alpha \in \{0,1\}^{r}}\mu (P^{\alpha })\\&=\sum _{\beta \in \{0,1\}^{r-1}}\left(\mu (P^{(0,\beta )})+\mu (P^{(1,\beta )})\right)=0\end{aligned}}$。$\Box$

证明 4:

我们从二项式定理和组合学中证明引理。

令 $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$。从组合学中，我们注意到对于 $m\leq r$，存在 ${\binom {m}{r}}$ 种不同的方法来选择一个子集 $I\subseteq \{1,\ldots ,r\}$，使得 $|I|=m$。定义 $\alpha _{I}=(\alpha _{1},\ldots ,\alpha _{r})\in \{0,1\}^{r}$，其中 $\alpha _{j}=1\Leftrightarrow j\in I$。那么，根据二项式定理

${\begin{aligned}E*\mu (n)&=\sum _{d|n}\mu (d)\\&=\sum _{I\subseteq \{1,\ldots ,r\}}\mu (P^{\alpha _{I}})\\&=\sum _{I\subseteq \{1,\ldots ,r\}}(-1)^{|I|}\\&=\sum _{j=0}^{r}{\binom {j}{r}}(-1)^{j}1^{j}=(1-1)^{r}=0\end{aligned}}$.$\Box$

欧拉函数公式

引理 2.11 (高斯 1801):

$\forall n\in \mathbb {N} :n=\sum _{d|n}\varphi (d)$.

证明 1:

我们使用下面证明的莫比乌斯反演公式（不使用这个引理），以及引理 2.10。

我们有 $\sum _{d|n}\varphi (d)=S_{\varphi }(n)$，因此根据莫比乌斯反演公式，$\varphi =\mu *S_{\varphi }$。另一方面，

$\varphi (n)=\mu *I_{1}(n)$

根据引理 2.10。

因此，我们得到 $\mu *S_{\varphi }=\mu *I_{1}$，通过约去 $\mu$（算术函数形成一个积分域），我们得到这个引理。$\Box$

证明 2:

我们使用下面证明的莫比乌斯反演公式的逆命题（不使用这个引理），以及引理 2.10。

根据引理 2.10，由梅比乌斯反演公式的逆定理可得 $\varphi (n)=\mu *I_{1}(n)$，因此 $I_{1}(n)=S_{\varphi }(n)$.$\Box$

证明 3:

我们通过双重计数来证明这个引理。

首先注意到，存在 $n$ 个形如 ${\frac {m}{n}}$ 的分数，其中 $1\leq m\leq n$。

现在我们证明这种形式的分数也有$\sum _{d|n}\varphi (d)$个。事实上，每个分数${\frac {m}{n}}$，$1\leq m\leq n$可以约分为${\frac {b}{d}}$，其中$\gcd(b,d)=1$。$d$是$n$的因数，因为它是通过将$n$除以$d$得到的。此外，对于$n$的每个因数$d$，根据$\varphi$的定义，恰好存在$\varphi (d)$个这样的分数。$\Box$

证明 4:

我们用集合论的方法证明这个引理。

定义$S_{n,d}:=\{1\leq l\leq n|\gcd(d,l)=1\}$。那么$S_{n,d}=\{dk|1\leq k\leq n/d,\gcd(k,n)=1\}=dS_{n/d,1}$。因为$|S_{n/d,1}|=\varphi (n/d)$，并且$\{1,\ldots ,n\}$是集合$S_{n,d},d|n$的互斥并，因此我们有

$n=\sum _{d|n}|S_{n,d}|=\sum _{d|n}d\varphi \left({\frac {n}{d}}\right)$.$\Box$

下一个定理包含了乘性函数最重要的例子之一。

定理 2.12 (欧拉 1761):

欧拉的 φ 函数是乘性的。

证明 1:

我们使用双重计数法 (由 克罗内克 提出) 来证明该定理。

根据 $\varphi$ 的定义，存在 $\varphi (m)\varphi (n)$ 个形如

${\frac {k}{m}}+{\frac {l}{n}},1\leq k\leq m,1\leq l\leq n$,

的和，其中两个加数都是最简的。我们断言存在一个双射

$\left\{{\frac {k}{m}}+{\frac {l}{n}}{\big |}1\leq k\leq m,1\leq l\leq n,{\frac {k}{m}},{\frac {l}{n}}{\text{ reduced}}\right\}\to \left\{{\frac {r}{mn}}{\big |}1\leq r\leq {\frac {r}{mn}}{\text{ reduced}}\right\}$.

由此可得 $\varphi (m)\varphi (n)=\varphi (mn)$.

我们断言，这样的双射由 ${\frac {k}{m}}+{\frac {l}{n}}\mapsto {\frac {nk+ml\mod mn}{nm}}$ 给出。

良定义性：设 ${\frac {k}{m}}$，${\frac {l}{n}}$ 是最简的。那么

${\frac {k}{m}}+{\frac {l}{n}}={\frac {kn+lm\mod mn}{nm}}$

也减少了，因为如果$p|(nm)$，那么不失一般性$p|n$，并且从$p|(kn+lm-cnm)$ 遵循$p|l$ 或者 $p|m$。在这两种情况下，我们都得到一个矛盾，要么是$\gcd(m,n)=1$ 或者 ${\frac {l}{n}}$ 被简化了。

满射性：令${\frac {r}{mn}}$ 被简化。使用欧几里得算法，我们找到$a,b\in \mathbb {N}$ 使得 $an+bm=1$。那么 $ran+rbm=r$。定义 $k=ra\mod m$，$l=rb\mod n$。那么

$kn+lm=(ra+tm)n+(rb+sn)m\equiv r\mod mn$.

单射性：令$kn+lm\equiv k'n+l'm\mod mn$。我们证明 $k=k'$；$l=l'$ 的证明是一样的。

事实上，从 $kn+lm\equiv k'n+l'm\mod mn$ 可以得出 $kn\equiv k'n\mod m$，并且由于 $\gcd(m,n)=1$，$n$ 在模 $m$ 意义下可逆，因此我们可以将该逆元乘以右侧以得到 $k\equiv k'\mod m$。由于 $1\leq k,k'\leq m$，结论得证。$\Box$

证明 2:

我们根据中国剩余定理来证明这个定理。

令 $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$。根据中国剩余定理，我们得到一个环同构

$\mathbb {Z} /n\to \mathbb {Z} /p_{1}^{k_{1}}\times \cdots \times \mathbb {Z} /p_{r}^{k_{r}}$,

它诱导出一个群同构

$(\mathbb {Z} /n)^{\times }\to \left(\mathbb {Z} /p_{1}^{k_{1}}\right)^{\times }\times \cdots \times \left(\mathbb {Z} /p_{r}^{k_{r}}\right)^{\times }$.

因此，$\left|(\mathbb {Z} /n)^{*}\right|=\prod _{j=1}^{r}\left|\left(\mathbb {Z} /p_{j}^{k_{j}}\right)^{*}\right|$，并且从$\forall m\in \mathbb {N} :\varphi (m)=\left|(\mathbb {Z} /m)^{*}\right|$ 遵循该断言。$\Box$

证明 3：我们根据引理 2.11 和归纳法（由Hensel给出）证明该定理。

设 $m,n\in \mathbb {N}$ 使得 $\gcd(m,n)=1$。根据引理 2.11，我们有 $m=\sum _{e|m}\varphi (e)$ 和 $n=\sum _{d|m}\varphi (d)$，因此

$mn=\varphi (m)\varphi (n)+\varphi (m)\sum _{d|n,d<n}\varphi (d)+\varphi (n)\sum _{e|m,e<m}\varphi (e)+\sum _{d|n,e|m \atop d<n,e<m}\varphi (d)\varphi (e)$.

此外，根据引理 2.11 和定理 2.8 证明中的双射，

$mn=\sum _{f|mn}\varphi (f)=\sum _{e|m,d|n}\varphi (ed)$.

通过对 $ed,en,md<mn$ 进行归纳，因此我们有

$mn=\varphi (mn)+\varphi (m)\sum _{d|n}\varphi (d)+\varphi (n)\sum _{e|m}\varphi (e)+\sum _{e|m,d|n \atop e<m,d<n}\varphi (e)\varphi (d)$.$\Box$

证明 4：我们从引理 2.11 和莫比乌斯反演公式证明该定理。

实际上，从引理 2.10 和莫比乌斯反演公式，我们得到

$\varphi =\mu *I_{1}$,

这就是为什么 $\varphi$ 作为两个积性函数的卷积是积性的。$\Box$

证明 5：我们从欧拉积公式证明该定理。

实际上，如果 $m=P^{\kappa }$ 且 $n=Q^{\iota }$，且 $\gcd(m,n)=1$，则 $P\cap Q=\emptyset$，因此

$\prod _{p|n}(p^{\kappa _{p}}-p^{\kappa _{p}-1})\prod _{q|n}(q^{\iota }-q^{\iota _{q}-1})=\varphi (mn)$.$\Box$

定理 2.15 (莫比乌斯反演公式):

令 $f$ 是一个算术函数，并定义

$S_{f}(n):=\sum _{d|n}f(d)=f*E(n)$.

那么

$f=\mu *S_{f}=\sum _{d|n}\mu (d)S_{f}\left({\frac {n}{d}}\right)$.

证明:

根据引理 2.14 和卷积的结合律，

$\mu *S_{f}=\mu *f*E=\mu *E*f=\delta *f=f$.$\Box$

定理 2.16（欧拉函数的乘积公式）:

令 $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$，其中 $p_{1},\ldots ,p_{r}$ 是成对不同的质数，并且 $k_{1},\ldots ,k_{r}\in \mathbb {N}$（回顾一下，根据算术基本定理，每个数字都有这样的分解）。那么

$\varphi (n)=n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)$.

证明 1:

我们根据引理 2.10 和 $\varphi$ 是可乘的这一事实来证明该定理。

事实上，令 $p$ 是一个质数，并且令 $k\in \mathbb {N}$。那么 $\varphi (p^{k})=p^{k}-p^{k-1}$，因为

$\varphi (p^{k})=(\mu *I_{1})(p^{k})=\sum _{j=0}^{k}\mu (p^{j})p^{k-j}$

根据引理 2.10。因此，

$\varphi (n)=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)=n\prod _{j=1}^{r}$,

其中后一个等式来自于

${\begin{aligned}n\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)&=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)\\&=\prod _{j=1}^{r}p_{j}^{k_{j}}\left(1-{\frac {1}{p_{j}}}\right)\\&=\prod _{j=1}^{r}\left(p_{j}^{k_{j}}-p_{j}^{k_{j}-1}\right)\end{aligned}}$.$\Box$

证明 2:

我们用概率论的方法证明这个恒等式。

设 $n\in \mathbb {N}$，$n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$. 选择 $\Omega =\{1,\ldots ,n\}$，${\mathcal {F}}=2^{\Omega }$，$P(A):={\frac {|A|}{n}}$. 对于 $j\in \{1,\ldots ,r\}$ 定义事件 $E_{p_{j}}:=\{1\leq k\leq n|p_{j}|n\}$. 那么我们有

$P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)={\frac {\varphi (n)}{n}}$.

另一方面，对于每个 $J=\{j_{1},\ldots ,j_{l}\}\subseteq \{1,\ldots ,r\}$，我们有

${\begin{aligned}P\left(E_{p_{j_{1}}}\cap \cdots \cap E_{p_{j_{1}}}\right)&=P\left(\left\{1\leq k\leq n{\big |}\prod _{j\in J}p_{j}|k\right\}\right)\\&={\frac {1}{\prod _{j\in J}p_{j}}}=\prod _{j\in J}P\left(E_{p_{j}}\right)\end{aligned}}$.

因此，可以得出结论，$E_{p_{1}},\ldots ,E_{p_{r}}$ 是独立的。但是，由于事件独立当且仅当它们的补集独立，我们得到

${\frac {\varphi (n)}{n}}=P\left({\overline {E_{p_{1}}}}\cap \cdots \cap {\overline {E_{p_{r}}}}\right)=P\left({\overline {E_{p_{1}}}})\right)\cdots P\left({\overline {E_{p_{r}}}}\right)=\prod _{j=1}^{r}\left(1-{\frac {1}{p_{j}}}\right)$.$\Box$

证明 3:

我们从莫比乌斯反演公式以及引理 2.9 和 2.10 证明该恒等式。

但是根据莫比乌斯反演公式，并且由于根据引理 2.10 $S_{\varphi }=I_{1}$,

$\sum _{d|n}\mu (d){\frac {n}{d}}=\mu *S_{\varphi }(n)=\varphi (n)$.$\Box$

证明 4:

我们从容斥原理 证明该恒等式。

事实上，根据德摩根定律之一以及容斥原理，对于集合 $A_{1},\ldots ,A_{r}\subseteq S$

${\begin{aligned}\left|\bigcap _{j=1}^{r}A_{j}\right|&=\left|S\setminus \bigcup _{j=1}^{r}\left(S\setminus A_{j}\right)\right|\\&=|S|-\left|\bigcup _{j=1}^{r}\left(S\setminus A_{j}\right)\right|\\&=|S|+\sum _{\emptyset \neq J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|\\&=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|\end{aligned}}$,

其中，我们使用空交集等于全集的约定 $S$。现在令 $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$，并定义 $S=\{m|1\leq m\leq n\}$ 和 $A_{j}:=\{l\in S|p_{j}\not |l\}$，对于 $1\leq j\leq r$。由于

$\varphi (n)=\left|\bigcap _{j=1}^{r}A_{j}\right|$,

我们有

$\varphi (n)=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|$.

但是对于每个 $J\subseteq \{1,\ldots ,r\}$，我们有

${\begin{aligned}\left|\bigcap _{j\in J}\left(S\setminus A_{j}\right)\right|&=\left\{1\leq l\leq n{\big |}\forall j\in J:p_{j}|l\right\}\\&=\left\{1\leq l\leq n{\big |}\left(\prod _{j\in J}p_{j}\right)|l\right\}={\frac {n}{\prod _{j\in J}p_{j}}}\end{aligned}}$.

因此

$\varphi (n)=n\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}$,

因为

$\prod {m=1}^{r}\left(1-{\frac {1}{p_{m}}}\right)=\sum _{J\subseteq \{1,\ldots ,r\}}(-1)^{|J|}{\frac {1}{\prod _{j\in J}p_{j}}}$,

定理得证。$\Box$

冯·曼戈尔特函数的公式

定理 8.? (Selberg 等式):