欧拉函数

此条目页的主题是小于等于n的正整数中与n互质的数的数目。关于形式为$\phi (q)=\prod _{k=1}^{\infty }(1-q^{k})$的函数，请见“欧拉函数 (复变函数)”。

在数论中，对正整数n，欧拉函数$\varphi (n)$是小于等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

当n为1至1000的整数时$\varphi (n)$的值

例如$\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) for 1 ≤ n ≤ 100

+	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}\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}n+qt_{2}m\ (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}}$，则

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

即费马小定理。

欧拉商数

欧拉商数（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)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)$

其中对任意正数k而言，误差项R至多与x/(log x)^k成比例。

目前已知对于任意的δ < 0.55655而言，有无限多个m，其重复度超过m^δ。

Ford定理

Ford (1999)证明说对于任意整数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\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}}$

未解决问题

莱默的欧拉函数问题

主条目：莱默的欧拉函数问题

若p是质数，则有φ(p) = p − 1。1932年，德里克·亨利·莱默问说是否有合成数n使得φ(n) 整除n − 1。目前未知是否有这样的数存在。

1933年莱默证明说若有这样的$n$，那么$n$必然是奇数、必然是无平方因子数，且必然有至少七个不同的质因数（$\omega (n)\geq 7$）。1980年，Cohen和Hagis证明了说，若这样的$n$存在，则$n>10^{20}$且$n$有至少14个不同的质因数（$\omega (n)\geq 14$）；此外，Hagis证明了说若这样的$n$存在且可被3除尽，那么$n>10^{1937042}$且$n$有至少298848个不同的质因数（$\omega (n)\geq 298848$）。

卡迈克尔猜想的欧拉函数猜想

主条目：卡迈克尔猜想的欧拉函数猜想

此猜想认为说不存在正整数n，使得对于所有其他的m而言，在m ≠ n的状况下必有φ(m) ≠ φ(n)。可见上述Ford定理一节的说明。

若有一个如此的反例存在，就必有无限多的反例存在，而最小的可能反例，在十进制下，其位数超过一百亿。

黎曼猜想

黎曼猜想成立，当且仅当以下不等式对所有的n ≥ p₁₂₀₅₆₉#成立。此处的p₁₂₀₅₆₉#是最初的120569个质数的乘积：

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

此处的γ是欧拉常数。

程式代码

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