欧拉函数

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

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

例如Template:計算結果，因為1、3、5和7均與8互質。

欧拉函数实际上是模n的同余类所构成的乘法群（即环$\mathbb{Z}/n\mathbb{Z}$的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起構成了欧拉定理的證明。

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

1736年，欧拉證明了费马小定理：

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

然後欧拉予以一般化：

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

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

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

欧拉函數的值

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

Template:Math for Template:Math

+	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$為質因子的次數），則歐拉函數在該處的值為

$\phi (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),$

亦可等價地寫成

$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_r}).$

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

質數冪處取值

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

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

積性

歐拉函數是積性函數，即是说若m,n互質，則$\phi (mn)=\phi (m)\phi (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$互質。

由中國剩餘定理，方程組

$\{\begin{array}{c}N\equiv p(\mathrm{mod}m)\\ N\equiv q(\mathrm{mod}n)\end{array}$

的通解可以寫成$N=kmn+p{t}_{1}n+q{t}_{2}m(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$一一對應。

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

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

公式的證明

結合以上兩小節的結果可得：若$n$有質因數分解式$n=p_1^{k_1}{p}_2^{k_2}\cdots p_r^{k_r}$，則

-{zh-hant: $\begin{array}{cc}\phi (n)& =\phi \left(\prod _{i=1}^r{p}_i^{k_i}\right)\\ & =\prod _{i=1}^r\phi \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(1-\frac{1}{p_i}).\end{array}$; zh-hans: $\begin{array}{cc}\phi (n)& =\phi \left(\prod _{i=1}^r{p}_i^{k_i}\right)\\ & =\prod _{i=1}^r\phi \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(1-\frac{1}{p_i}).\end{array}$; }-

例子

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

$\phi (72)=\phi (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的欧拉函数$\phi (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}\phi (d)=n$

其中的d为n的正约数。

运用默比乌斯反转公式来“翻转”这个和，就可以得到另一个关于$\phi (n)$的公式：

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

其中 μ 是所谓的默比乌斯函数，定义在正整数上。

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

$a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

即欧拉定理。

这个定理可以由群论中的拉格朗日定理得出，因为任意与m互质的a都属于环 $\mathbb{Z}/n\mathbb{Z}$ 的单位元组成的乘法群$\mathbb{Z}/n{\mathbb{Z}}^{\times }$

當m是質數p時，此式則為：

$a^{p-1}\equiv 1(\mathrm{mod}p)$

即費馬小定理。

歐拉商數

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

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

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

其中Template:Math。

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

$|\{n:\phi (n)\le x\}|=\frac{\zeta (2)\zeta (3)}{\zeta (6)}\cdot x+R(x)$

其中對任意正數Template:Mvar而言，誤差項Template:Mvar至多與Template:Math成比例。

目前已知對於任意的Template:Math而言，有無限多個Template:Mvar，其重複度超過Template:Math。

Ford定理

Template:Harvtxt證明說對於任意整數Template:Math而言，總存在一個歐拉商數Template:Mvar，其重複度為Template:Mvar，也就是說總有數字使得這等式Template:Math有剛好Template:Mvar個解。這結果由瓦茨瓦夫·謝爾賓斯基所猜測，且是Template:Link-en的一個結果。事實上，對於任何出現的重複度而言，該重複度會出現無限多次。

然而，沒有任何數字Template:Mvar的重複度為Template:Math。Template:Link-en講的是沒有Template:Mvar的重複度為Template:Math。

完全歐拉商數

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

生成函数

以下两个由欧拉函数生成的级数都是来自于上节所给出的性质：$\sum _{d|n}\phi (d)=n$。

由$\phi$(n)生成的狄利克雷级数是：

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

其中ζ(s)是黎曼ζ函数。推导过程如下：

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

$.=\sum _{h=1}^{\mathrm{\infty }}(\sum _{fg=h}1\cdot \phi (g))\frac{1}{h^s}$

$.=\sum _{h=1}^{\mathrm{\infty }}(\sum _{fg=h}\phi (g))\frac{1}{h^s}=\sum _{h=1}^{\mathrm{\infty }}(\sum _{d|h}\phi (d))\frac{1}{h^s}$

使用开始时的等式，就得到：$\sum _{h=1}^{\mathrm{\infty }}(\sum _{d|h}\phi (d))\frac{1}{h^s}=\sum _{h=1}^{\mathrm{\infty }}\frac{h}{h^s}$

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

欧拉函数生成的朗贝级数如下：

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

其对于满足 |q|<1 的q收敛。

推导如下：

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\sum _{n=1}^{\mathrm{\infty }}\phi (n)\sum _{r\ge 1}{q}^{rn}$

后者等价于：

$\sum _{k\ge 1}{q}^k\sum _{n|k}\phi (n)=\sum _{k\ge 1}k{q}^k=\frac{q}{(1-q{)}^2}.$

欧拉函数的走势

随着n变大，估计$\phi (n)$ 的值是一件很难的事。当n为质数时，$\phi (n)=n-1$，但有时$\phi (n)$又与n差得很远。

在n足够大时，有估计：

对每个 ε > 0，都有n > N(ε)使得 $n^{1-\epsilon }<\phi (n)<n$

如果考虑比值：

$\phi (n)/n,$

由以上已经提到的公式，可以得到其值等于类似$1-p^{-1}$的项的乘积。因此，使比值小的n将是两两不同的质数的乘积。由素数定理可以知道，常数 ε 可以被替换为：

$C\log \log n/\log n.$

$\phi$就平均值的意义上来说是与n很相近的，因为：

$\frac{1}{n^2}\sum _{k=1}^n\phi (k)=\frac{3}{{\pi }^2}+𝒪\left(\frac{\log n}{n}\right)$

其中的O表示大O符号。这个等式也可以说明在集合 {1, 2, ..., n} 中随机选取两个数，则当n趋于无穷大时，它们互质的概率趋于 $6/{\pi }^2$ 。一个相关的结果是比值$\phi (n)/n$的平均值：

$\frac{1}{n}\sum _{k=1}^n\frac{\phi (k)}{k}=\frac{6}{{\pi }^2}+𝒪\left(\frac{\log n}{n}\right).$

其他与欧拉函数有关的等式

1. $\phi \left(n^m\right)=n^{m-1}\phi (n)$
2. $\mathrm{\forall }a\in N,\mathrm{\forall }n\in N,\mathrm{\exists }l\in N$ 使得 $[(a>1\wedge n>1)\to (l|\phi (a^n-1)\wedge l\ge n)]$
3. $\mathrm{\forall }a\in N,\mathrm{\forall }n\in N,\mathrm{\exists }l\in N$ 使得 $[(a>1\wedge n>6\wedge 4\nmid n)\to (l|\phi (a^n-1)\wedge l\ge 2n)]$
4. $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}$
5. $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,n)=1}}k=\frac{1}{2}n\phi (n)\text{ for }n>1$
6. $\sum _{k=1}^n\phi (k)=\frac{1}{2}(1+\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\rfloor }^2)$
7. $\sum _{k=1}^n\frac{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor$
8. $\sum _{k=1}^n\frac{k}{\phi (k)}=𝒪(n)$
9. $\sum _{k=1}^n\frac{1}{\phi (k)}=𝒪(\log (n))$

与欧拉函数有关的不等式

1. $\phi (n)>\frac{n}{e^{\gamma }\log \log n+\frac{3}{\log \log n}}$，其中n > 2，γ 为欧拉-马歇罗尼常数。
2. $\phi (n)\ge \sqrt{\frac{n}{2}}$ ，其中n > 0。
3. 对整数n > 6，$\phi (n)\ge \sqrt{n}$。
4. 当n为质数时，显然有$\phi (n)=n-1$。对于合数的n，则有：

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

未解決問題

萊默的歐拉函數問題

若Template:Mvar是質數，則有Template:Math。1932年，德里克·亨利·萊默問說是否有合成數Template:Mvar使得Template:Math整除Template:Math。目前未知是否有這樣的數存在。

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

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

此猜想認為說不存在正整數Template:Mvar，使得對於所有其他的Template:Mvar而言，在Template:Math的狀況下必有Template:Math。可見上述Ford定理一節的說明。

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

黎曼猜想

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

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

此處的Template:Mvar是歐拉常數。

程式代码

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. Template:Wayback

• 柯召，孙琦：数论讲义（上册），第二版，高等教育出版社，2001