欧拉商数

在數論中，對正整數 _n_，**歐拉函數** $\varphi (n)$ 是小於等於 _n_ 的正整數中與 _n_ 互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為 **φ 函數**（由高斯所命名）或是**歐拉總計函數**（totient function，由西爾維斯特所命名）。

例如 $\varphi \left(8\right)=4$ ，因為 1、3、5 和 7 均與 8 互質。

歐拉函數實際上是模 _n_ 的同餘類所構成的乘法群（即環 $\mathbb {Z} /n\mathbb {Z} $ 的所有單位元組成的乘法群）的階。這個性質與拉格朗日定理一起構成了歐拉定理的證明。

## 歷史：歐拉函數與費馬小定理

1736 年，歐拉證明了費馬小定理：

　
: 假若 $p$ 為質數， $a$ 為任意正整數，那麼 $a^{p}-a$ 可被 $p$ 整除。

然後歐拉予以一般化：

　
: 假若 $a$ 與 $n$ 互質，那麼 $a^{\varphi (n)}-1$ 可被 $n$ 整除。亦即， $a^{\varphi (n)}\equiv 1{\pmod {n}}$ 。

其中 $\varphi (n)$ 即為歐拉總計函數。如果 $n$ 為質數，那麼 $\varphi (n)=n-1$ ，因此，有高斯的版本：

　
: 假若 $p$ 為質數， $a$ 與 $p$ 互質（ $a$ 不是 $p$ 的倍數），那麼 $a^{p-1}\equiv 1{\pmod {p}}$ 。

## 歐拉函數的值

以下為 $n$ 為 $1$ 至 $100$ 時，對應 $\varphi (n)$ 的值

　
:

若 $n$ 有標準分解 $p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}$ （其中各 $p_{i}$ 為互異的質因子，各 $k_{i}\geq 1$ 為質因子的次數），則歐拉函數在該處的值為

　
: $\varphi (n)=p_{1}^{k_{1}-1}p_{2}^{k_{2}-1}\cdots p_{r}^{k_{r}-1}(p_{1}-1)(p_{2}-1)\cdots (p_{r}-1),$

亦可等價地寫成

　
: $\varphi (n)=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).$

此結果可由 $\varphi $ 在質數冪處的取值，以及其**積性**得到。

### 質數冪處取值

最簡單的情況有 $\varphi (1)=1$ （小於等於 1 的正整數中唯一和 1 互質的數就是 1 本身）。

一般地，若 _n_ 是質數 _p_ 的 _k_ 次冪，則 $\varphi (n)=\varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}$ ，因為除了 _p_ 的倍數外，其他數都跟 _n_ 互質。

### 積性

歐拉函數是積性函數，即是說若 _m_,_n_ 互質，則 $\varphi (mn)=\varphi (m)\varphi (n)$ 。使用中國剩餘定理有較簡略的證明：設 _A_, _B_, _C_ 是跟 _m_, _n_, _mn_ 互質的數的集，據中國剩餘定理， $A\times B$ 和 $C$ 可建立雙射（一一對應）關係，因此兩者元素個數相等。

較詳細的證明如下：

設 $N<mn$ ，且 $N=k_{1}m+p=k_{2}n+q$ 。若 $N$ 與 $mn$ 互質，則 $N$ 與 $m$ 、 $n$ 均互質。又因為 $(k_{1}m+p,m)=(p,m),(k_{2}n+q,n)=(q,n)$ ，若 $p,q$ 分別與 $m,n$ 互質，則 $N$ 一定和 $mn$ 互質。反之亦然，即若 $N$ 與 $mn$ 互質，則亦有 $p,q$ 分別與 $m,n$ 互質。

由中國剩餘定理，方程組

　
: $\left\{{\begin{matrix}N\equiv p{\pmod {m}}\\N\equiv q{\pmod {n}}\\\end{matrix}}\right.$

的通解可以寫成 $N=kmn+pt_{1}m+qt_{2}n\ (k\in \mathbb {Z} ),$ 其中 $t_{1},t_{2}$ 為固定的整數，故二元組 $(p,q)$ （要滿足 $0<p\leq m,\ 0<q\leq n,\ (p,m)=1,\ (q,n)=1$ ）與小於 $mn$ 且與 $mn$ 互質的正整數 $N$ 一一對應。

由 $\varphi $ 的定義（和乘法原理），前一種數對 $(p,q)$ 的個數為 $\varphi (m)\varphi (n)$ 。而後一種數 $N$ 的個數為 $\varphi (mn)$ 。

所以， $\varphi (mn)=\varphi (m)\varphi (n).$

### 公式的證明

結合以上兩小節的結果可得：若 $n$ 有質因數分解式 $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}$ ，則

　
: ${\begin{aligned}\varphi (n)&=\varphi \left(\prod _{i=1}^{r}p_{i}^{k_{i}}\right)\\&=\prod _{i=1}^{r}\varphi \left(p_{i}^{k_{i}}\right)&{\text{（ 積 性 ）}}\\&=\prod _{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)&{\text{（ 質 數 冪 處 取 值 ）}}\\&=n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).\end{aligned}}$

### 例子

計算 $72=2^{3}\times 3^{2}$ 的歐拉函數值：

　
: $\varphi (72)=\varphi (2^{3}\times 3^{2})=2^{3-1}(2-1)\times 3^{2-1}(3-1)=2^{2}\times 1\times 3\times 2=24.$

## 性質

_n_ 的歐拉函數 $\varphi (n)$ 也是循環群 _C_n 的生成元的個數（也是 _n_ 階分圓多項式的次數）。_C_n 中每個元素都能生成 _C_n 的一個子群，即必然是某個子群的生成元。而且按照定義，不同的子群不可能有相同的生成元。此外， _C_n 的所有子群都具有 _C_d 的形式，其中 _d_ 整除 _n_（記作 _d_ | _n_）。因此只要考察 _n_ 的所有因數 _d_，將 _C_d 的生成元個數相加，就將得到 _C_n 的元素總個數：_n_。也就是說：

　
: $\sum _{d\mid n}\varphi (d)=n$

其中的 _d_ 為 _n_ 的正約數。

運用默比烏斯反轉公式來「翻轉」這個和，就可以得到另一個關於 $\varphi (n)$ 的公式：

　
: $\varphi (n)=\sum _{d\mid n}d\cdot \mu (n/d)$

其中 μ 是所謂的默比烏斯函數，定義在正整數上。

對任何兩個互質的正整數 _a_, _m_（即 gcd (_a_,_m_) = 1）， $m\geq 2$ ，有

　
: $a^{\varphi (m)}\equiv 1{\pmod {m}}$

即歐拉定理。

這個定理可以由群論中的拉格朗日定理得出，因為任意與 _m_ 互質的 _a_ 都屬於環 $\mathbb {Z} /n\mathbb {Z} $ 的單位元組成的乘法群 $\mathbb {Z} /n\mathbb {Z} ^{\times }$

當 _m_ 是質數 _p_ 時，此式則為：

　
: $a^{p-1}\equiv 1{\pmod {p}}$

即費馬小定理。

## 生成函數

以下兩個由歐拉函數生成的級數都是來自於上節所給出的性質： $\sum _{d|n}\varphi (d)=n$ 。

由 $\varphi $ (_n_) 生成的狄利克雷級數是：

　
: $\sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.$

其中 ζ(_s_) 是黎曼 ζ 函數。推導過程如下：

　
: $\zeta (s)\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}=\left(\sum _{g=1}^{\infty }{\frac {1}{g^{s}}}\right)\left(\sum _{f=1}^{\infty }{\frac {\varphi (f)}{f^{s}}}\right)$

　
: $.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum _{h=1}^{\infty }\left(\sum _{fg=h}1\cdot \varphi (g)\right){\frac {1}{h^{s}}}$

　
: $.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum _{h=1}^{\infty }\left(\sum _{fg=h}\varphi (g)\right){\frac {1}{h^{s}}}=\sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}$

　
: 使用開始時的等式，就得到： $\sum _{h=1}^{\infty }\left(\sum _{d|h}\varphi (d)\right){\frac {1}{h^{s}}}=\sum _{h=1}^{\infty }{\frac {h}{h^{s}}}$

　
: 於是 $\sum _{h=1}^{\infty }{\frac {h}{h^{s}}}=\zeta (s-1)$

歐拉函數生成的朗貝級數如下：

　
: $\sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}$

其對於滿足 |_q_|<1 的 _q_ 收斂。

推導如下：

　
: $\sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}=\sum _{n=1}^{\infty }\varphi (n)\sum _{r\geq 1}q^{rn}$

後者等價於：

　
: $\sum _{k\geq 1}q^{k}\sum _{n|k}\varphi (n)=\sum _{k\geq 1}kq^{k}={\frac {q}{(1-q)^{2}}}.$

## 歐拉函數的走勢

隨著 _n_ 變大，估計 $\varphi (n)$ 的值是一件很難的事。當 _n_ 為質數時， $\varphi (n)=n-1$ ，但有時 $\varphi (n)$ 又與 _n_ 差得很遠。

在 _n_ 足夠大時，有估計：

　
: 對每個 ε > 0，都有 _n_ > _N_(ε) 使得 $\,n^{1-\varepsilon }<\varphi (n)<n$

如果考慮比值：

　
: $\,\varphi (n)/n,$

由以上已經提到的公式，可以得到其值等於類似 $1-p^{-1}$ 的項的乘積。因此，使比值小的 _n_ 將是兩兩不同的質數的乘積。由素數定理可以知道，常數 ε 可以被替換為：

　
: $C\,\log \log n/\log n.$

 $\varphi $ 就平均值的意義上來說是與 _n_ 很相近的，因為：

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

其中的 _O_ 表示大 O 符號。這個等式也可以說明在集合 {1, 2, ..., _n_} 中隨機選取兩個數，則當 _n_ 趨於無窮大時，它們互質的概率趨於 $6/\pi ^{2}$ 。一個相關的結果是比值 $\varphi (n)/n$ 的平均值：

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

## 其他與歐拉函數有關的等式

 1. $\;\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)$
2. $\forall a\in N,\forall n\in N,\ \exists l\in N$ 使得 $[(a>1\land n>1)\rightarrow (l|\varphi (a^{n}-1)\land l\geq n)]$
3. $\forall a\in N,\forall n\in N,\ \exists l\in N$ 使得 $[(a>1\land n>6\land 4\nmid n)\rightarrow (l|\varphi (a^{n}-1)\land l\geq 2n)]$
4. $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$
5. $\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\frac {1}{2}}n\varphi (n){\text{ for }}n>1$
6. $\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)$
7. $\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor $
8. $\sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\mathcal {O}}(n)$
9. $\sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\mathcal {O}}(\log(n))$

## 與歐拉函數有關的不等式

 1. $\varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}$ ，其中 _n_ > 2，γ 為歐拉 - 馬歇羅尼常數。
2. $\varphi (n)\geq {\sqrt {\frac {n}{2}}}$ ，其中 _n_ > 0。
3. 對整數 n > 6， $\varphi (n)\geq {\sqrt {n}}$ 。
4. 當 _n_ 為質數時，顯然有 $\varphi (n)=n-1$ 。對於合數的 _n_，則有：

　
: $\varphi (n)\leq n-{\sqrt {n}}$

## 程式代碼

### C++

## 參考來源

* Milton Abramowitz、Irene A. Stegun， _Handbook of Mathematical Functions_， (1964) Dover Publications , New York. ISBN 0-486-61272-4. 24.3.2 節.
* Eric Bach、Jeffrey Shallit， _Algorithmic Number Theory_, 卷 1, 1996, MIT Press. ISBN 0-262-02405-5, 8.8 節，234 頁.
* Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150 (1999), 283--311. （頁面存檔備份，存於網際網路檔案館）
* 柯召，孫琦：數論講義（上冊），第二版，高等教育出版社，2001

## 文獻來源

## 參考資料