歐拉函數

形式為$\phi(q)=\prod_{k=1}^\infty (1-q^k)$的函數

<image>

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

例如eulerphi(8)，因為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)$ 的值

+｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10

0｜1｜1｜2｜2｜4｜2｜6｜4｜6｜4

10｜10｜4｜12｜6｜8｜8｜16｜6｜18｜8

20｜12｜10｜22｜8｜20｜12｜18｜12｜28｜8

30｜30｜16｜20｜16｜24｜12｜36｜18｜24｜16

40｜40｜12｜42｜20｜24｜22｜46｜16｜42｜20

50｜32｜24｜52｜18｜40｜24｜36｜28｜58｜16

60｜60｜30｜36｜32｜48｜20｜66｜32｜44｜24

70｜70｜24｜72｜36｜40｜36｜60｜24｜78｜32

80｜54｜40｜82｜24｜64｜42｜56｜40｜88｜24

90｜72｜44｜60｜46｜72｜32｜96｜42｜60｜40

若$n$有標準分解$p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$（其中各$p_i$為互異的質因子，各$k_i \ge 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_1m+p=k_2n+q$。若$N$與$mn$互質，則$N$與$m$、$n$均互質。又因為$(k_1m+p,m)=(p,m),(k_2n+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_1n+qt_2m \ (k \in \mathbb Z),$ 其中$t_1, t_2$為固定的整數，故二元組$(p,q)$（要滿足$0 < p \le m,\ 0 < q \le 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}$，則

$$\quad\begin{align}\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{align}$$

### 例子

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

$$\varphi(72)=\varphi(2^3\times3^2)=2^{3-1}(2-1)\times3^{2-1}(3-1)=2^2\times1\times3\times2=24.$$

## 性質

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

$$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$$

即費馬小定理。

## 歐拉商數

歐拉商數（totient number）指的是歐拉函數的值，也就是說，若m是一個歐拉商數，那至少存在一個n，使得φ(n) = m。而歐拉商數m的「重複度」（valency或multiplicity），指的是這等式的解數。相對地，一個非歐拉商數指的是不是歐拉商數的自然數。顯然所有大於1的奇數都是非歐拉商數，此外也存有無限多的偶數是非歐拉商數，且所有的正整數都有一個倍數是非歐拉商數。

不大於x的歐拉商數個數可由以下公式給出：

$$\frac{x}{\log x}e^{ \big(C+o(1)\big)(\log\log\log x)^2 }$$

其中C = 0.8178146...。

考慮重複度，那麼不大於x的歐拉商數個數可由以下公式給出：

$$\Big\vert\{ n : \varphi(n) \le x \}\Big\vert = \frac{\zeta(2)\zeta(3)}{\zeta(6)} \cdot x + R(x)$$

其中對任意正數k而言，誤差項R至多與x成比例。

目前已知對於任意的δ < 0.55655而言，有無限多個m，其重複度超過mδ。

### Ford定理

證明說對於任意整數k ≥ 2而言，總存在一個歐拉商數m，其重複度為k，也就是說總有數字使得這等式φ(n) = m有剛好k個解。這結果由瓦茨瓦夫·謝爾賓斯基所猜測，且是Schinzel猜想H的一個結果。事實上，對於任何出現的重複度而言，該重複度會出現無限多次。

然而，沒有任何數字m的重複度為k = 1。卡邁克爾猜想的歐拉函數猜想講的是沒有m的重複度為k = 1。

### 完全歐拉商數

完全歐拉商數（perfect totient number）是一個等同於其歐拉函數迭代總和的整數，也就是說，如果將歐拉函數套用在一個正整數$n$之後，並將歐拉函數套用在如此所得的結果上，如此下去，直到最後得到1為止，並將這一系列的數給加總起來。若這總和為$n$，那麼$n$就是一個完全歐拉商數。

## 生成函數

以下兩個由歐拉函數生成的級數都是來自於上節所給出的性質：$\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\ge 1} q^{rn}$$

後者等價於：

$$\sum_{k\ge 1} q^k \sum_{n|k} \varphi(n) = \sum_{k\ge 1} k q^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).$$

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

- $$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n)$$
- $\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) ]$
- $\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) ]$
- $$\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}$$
- $$\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \frac{1}{2}n\varphi(n)\text{ for }n>1$$
- $$\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)$$
- $$\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor$$
- $$\sum_{k=1}^n\frac{k}{\varphi(k)} = \mathcal{O}(n)$$
- $$\sum_{k=1}^n\frac{1}{\varphi(k)} = \mathcal{O}(\log(n))$$

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

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

$$\varphi(n) \le n-\sqrt{n}$$

## 未解決問題

### 萊默的歐拉函數問題

若p是質數，則有φ(p) = p − 1。1932年，德里克·亨利·萊默問說是否有合成數n使得φ(n)整除n − 1。目前未知是否有這樣的數存在。

1933年萊默證明說若有這樣的$n$，那麼$n$必然是奇數、必然是無平方因子數，且必然有至少七個不同的質因數（$\omega(n)\ge7$）。1980年，Cohen和Hagis證明了說，若這樣的$n$存在，則$n > 10^{20}$且$n$有至少14個不同的質因數（$\omega(n)\ge14$）；此外，Hagis證明了說若這樣的$n$存在且可被3除盡，那麼$n > 10^{1937042}$且$n$有至少298848個不同的質因數（$\omega(n)\ge298848$）。

### 卡邁克爾猜想的歐拉函數猜想

此猜想認為說不存在正整數n，使得對於所有其他的m而言，在m ≠ n的狀況下必有φ(m) ≠ φ(n)。可見上述Ford定理一節的說明。

若有一個如此的反例存在，就必有無限多的反例存在，而最小的可能反例，在十進位下，其位數超過一百億。

### 黎曼猜想

黎曼猜想成立，當且僅當以下不等式對所有的n ≥ p120569#成立。此處的p120569#是最初的個質數的乘積：

$$\frac{n}{\varphi (n)}<e^\gamma \log\log n+\frac{e^\gamma (4+\gamma-\log 4\pi)}{\sqrt{\log n}}$$

此處的γ是歐拉常數。

## 程式代碼

### C++

```c++
template <typename T>
inline T phi(T n) {
    T ans = n;
    for (T i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
```

## 參考來源

- 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