欧拉函数

形式为$\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