數學/數論/尤拉函式的著名定理

此頁面提供了涉及尤拉函式 $\varphi (k)$ 和莫比烏斯函式 $\mu (k)$ 的恆等式的證明。

與n互質且小於等於n的整數之和

恆等式的證明

\sum _{1\leq k\leq n \atop (k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 2

利用以下事實

(k,n)=d\quad \Leftrightarrow \quad (n-k,n)=d

因為如果 $d|n$ 和 $d|k$ 則 $d|n-k$ ，如果 $d|n$ 和 $d|(n-k)$ 則 $d|n-(n-k)=k.$

這意味著對於 $n>2$ ，我們可以將與n互質的k分組為對

(k,n-k)\quad {\mbox{ where }}\quad k<n-k.

.

情況 $k=n/2$ 不會出現，因為當n為奇數時 $n/2$ 不是整數，當n為偶數時，我們有 $(n/2,n)=n/2>1$ ，因為我們假設 $n>2.$ 有

{\frac {\varphi (n)}{2}}

對，每對的元素之和為

k\;+\;n-k\;=n,

因此

\sum _{(k,n)=1}k={\frac {1}{2}}\,\varphi (n)\,n\quad {\mbox{ where }}\quad n\geq 3.

情況 $n=2$ 可以透過直接代入驗證，也可以包含在公式中。

涉及取整函式的尤拉函式恆等式的證明

恆等式的證明

\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor

是用數學歸納法對 $n$ 證明的。基本情況是 $n=1$ ，我們可以看到結論成立

\varphi (1)/1=1={\frac {\mu (1)}{1}}\left\lfloor 1\right\rfloor .

為了歸納步驟，我們需要證明

{\frac {\varphi (n+1)}{n+1}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left(\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \right)+{\frac {\mu (n+1)}{n+1}}.

關鍵觀察是

\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \;=\;{\begin{cases}1,&{\mbox{if }}k|(n+1)\\0,&{\mbox{otherwise, }}\end{cases}}

因此，這個和是

\sum _{k|n+1,\;k<n+1}{\frac {\mu (k)}{k}}+{\frac {\mu (n+1)}{n+1}}=\sum _{k|n+1}{\frac {\mu (k)}{k}}.

現在，事實是

\sum _{k|n+1}{\frac {\mu (k)}{k}}={\frac {\varphi (n+1)}{n+1}}

是一個基本的totient恆等式。要看到它成立，設 $p_{1}^{v_{1}}p_{2}^{v_{2}}\ldots p_{q}^{v_{q}}$ 是 n+1 的素數分解。那麼

{\frac {\varphi (n+1)}{n+1}}=\prod _{l=1}^{q}\left(1-{\frac {1}{p_{l}}}\right)=\sum _{k|n+1}{\frac {\mu (k)}{k}}

根據 $\mu (k).$ 的定義。這結束了證明。

另一種證明方法是將 ${\frac {\varphi (k)}{k}}=\sum _{d|k}{\frac {\mu (d)}{d}}$ 直接代入恆等式的左側，得到 $\sum _{k=1}^{n}\sum _{d|k}{\frac {\mu (d)}{d}}.$

現在我們問項 ${\begin{matrix}{\frac {\mu (d)}{d}}\end{matrix}}$ 在二重和中出現了多少次。答案是，它對於 $d$ 的每個倍數 $k$ 都會出現，但恰好有 ${\begin{matrix}\left\lfloor {\frac {n}{d}}\right\rfloor \end{matrix}}$ 個這樣的倍數，這意味著該和為

\sum _{d=1}^{n}{\frac {\mu (d)}{d}}\left\lfloor {\frac {n}{d}}\right\rfloor

如前所述。

過濾掉 ${\begin{matrix}\left\lfloor {\frac {n+1}{k}}\right\rfloor -\left\lfloor {\frac {n}{k}}\right\rfloor \end{matrix}}$ 的零值也可以用來證明恆等式

\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right).

基本情況是 $n=1$ ，我們有

\varphi (1)=1={\frac {1}{2}}\left(1+\mu (1)\left\lfloor {\frac {1}{1}}\right\rfloor ^{2}\right)

它成立。歸納步驟要求我們證明

\varphi (n+1)={\frac {1}{2}}\sum _{k=1}^{n}\mu (k)\left(\left\lfloor {\frac {n+1}{k}}\right\rfloor ^{2}-\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)\;+\;{\frac {1}{2}}\;\mu (n+1)\;\left\lfloor {\frac {n+1}{n+1}}\right\rfloor ^{2}.

接下來觀察

\left\lfloor {\frac {n+1}{k}}\right\rfloor ^{2}-\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\;=\;{\begin{cases}2{\frac {n+1}{k}}-1,&{\mbox{if }}k|(n+1)\\0,&{\mbox{otherwise.}}\end{cases}}

這給出了和的以下結果

{\frac {1}{2}}\sum _{k|n+1,\;k<n+1}\mu (k)\left(2{\frac {n+1}{k}}-1\right)\;+\;{\frac {1}{2}}\;\mu (n+1)={\frac {1}{2}}\sum _{k|n+1}\mu (k)\left(2\;{\frac {n+1}{k}}-1\right).

分別處理兩個內部項，我們得到

(n+1)\sum _{k|n+1}{\frac {\mu (k)}{k}}-{\frac {1}{2}}\sum _{k|n+1}\mu (k).

這兩個中的第一個精確地是 $\varphi (n+1)$ ，正如我們之前所見，第二個是零，這是根據莫比烏斯函式的基本性質（使用與上面相同的 $n+1$ 因式分解，我們有 ${\begin{matrix}\sum _{k|n+1}\mu (k)=\prod _{l=1}^{q}(1-1)=0\end{matrix}}$ 。）這完成了證明。

這個結果也可以用容斥原理來證明。將等式改寫為

-1+2\sum _{k=1}^{n}\varphi (k)=\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}.

現在我們看到，等式的左邊表示 [1,n] × [1,n] 中的格點 (a, b) 的數量，其中 a 和 b 互質。使用集合 $A_{p}$ ，其中 p 是小於或等於 n 的素數，表示兩個座標都可被 p 整除的點的集合，我們有

\left|\bigcup _{p}A_{p}\right|=\sum _{p}\left|A_{p}\right|\;-\;\sum _{p<q}\left|A_{p}\cap A_{q}\right|\;+\;\sum _{p<q<r}\left|A_{p}\cap A_{q}\cap A_{r}\right|\;-\;\cdots \;\pm \;\left|A_{p}\cap \;\cdots \;\cap A_{s}\right|.

這個公式計算了 a 和 b 不互質的點的對數。基數如下

\left|A_{p}\right|=\left\lfloor {\frac {n}{p}}\right\rfloor ^{2},\;\left|A_{p}\cap A_{q}\right|=\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2},\;\left|A_{p}\cap A_{q}\cap A_{r}\right|=\left\lfloor {\frac {n}{pqr}}\right\rfloor ^{2},\;\ldots

符號是 ${\begin{matrix}-\mu (pqr\cdots )\end{matrix}}$ ，因此具有互質座標的點的數量為

$\mu (1)\,n^{2}\;+\;\sum _{p}\mu (p)\left\lfloor {\frac {n}{p}}\right\rfloor ^{2}\;+\;\sum _{p<q}\mu (pq)\left\lfloor {\frac {n}{pq}}\right\rfloor ^{2}\;+\;\sum _{p<q<r}\mu (pqr)\left\lfloor {\frac {n}{pqr}}\right\rfloor ^{2}\;+\;\cdots$

但這正是 $\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}$ ，因此我們得到了結論。

尤拉函式的平均階

我們將使用上一節的最後一個公式來證明以下結果

{\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)

利用 $x-1<\lfloor x\rfloor \leq x$ ，我們得到上限

{\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k){\frac {n^{2}}{k^{2}}}\right)={\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}

以及下限

{\frac {1}{2n^{2}}}\left(1+\sum _{k=1}^{n}\mu (k)\left({\frac {n^{2}}{k^{2}}}-2{\frac {n}{k}}+1\right)\right)

即

{\frac {1}{2n^{2}}}+{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}+{\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)

處理最後兩項並利用第n個調和數的漸近展開，我們有

-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {\mu (k)}{k}}>-{\frac {1}{n}}\sum _{k=1}^{n}{\frac {1}{k}}=-{\frac {1}{n}}H_{n}>-{\frac {1}{n}}(\log n+1)

以及

{\frac {1}{2n^{2}}}\sum _{k=1}^{n}\mu (k)>-{\frac {1}{2n}}.

現在我們檢查上下界中各項的階數。項 ${\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}$ 是 ${\mathcal {O}}(1)$ ，與 $\zeta (2)$ 作比較可知，其中 $\zeta (s)$ 是黎曼ζ函式。下一個最大項是下界中的對數項。

到目前為止，我們已經證明了

{\frac {1}{n^{2}}}\sum _{k=1}^{n}\varphi (k)={\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}+{\mathcal {O}}\left({\frac {\log n}{n}}\right)

現在需要漸進地評估 ${\begin{matrix}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}$ ，我們已經看到它收斂。黎曼ζ函式的尤拉乘積為

\zeta (s)=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)^{-1}{\mbox{ for }}\Re (s)>1.

從莫比烏斯函式的定義可以立即得到

{\frac {1}{\zeta (s)}}=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n\geq 1}{\frac {\mu (n)}{n^{s}}}.

這意味著

{\frac {1}{2}}\sum _{k=1}^{n}{\frac {\mu (k)}{k^{2}}}={\frac {1}{2}}{\frac {1}{\zeta (2)}}+{\mathcal {O}}\left({\frac {1}{n}}\right)

其中積分 ${\begin{matrix}\int _{n+1}^{\infty }{\frac {1}{t^{2}}}dt\end{matrix}}$ 用於估計 ${\begin{matrix}\sum _{k>n}{\frac {\mu (k)}{k^{2}}}\end{matrix}}.$ 但 ${\begin{matrix}{\frac {1}{2}}{\frac {1}{\zeta (2)}}={\frac {3}{\pi ^{2}}}\end{matrix}}$ 並且我們已經證實了這一論點。