解析數論/數論函式公式

莫比烏斯 μ 函式的公式

引理 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 等式):