歐拉函數

此條目的主題是小於等於n的正整數中與n互質的數的數目。關於形式為${\displaystyle \phi (q)=\prod _{k=1}^{\infty }(1-q^{k})}$的函數，請見「歐拉函數 (複變函數)」。

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

當n為1至1000的整數時${\displaystyle \varphi (n)}$的值

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

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

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

1736年，歐拉證明了費馬小定理^[2]：

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

然後歐拉予以一般化：

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

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

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

歐拉函數的值

以下為${\displaystyle n}$ 為${\displaystyle 1}$至${\displaystyle 100}$時，對應${\displaystyle \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

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

${\displaystyle \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),}$

亦可等價地寫成

${\displaystyle \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).}$

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

質數冪處取值

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

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

積性

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

較詳細的證明如下：

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

由中國剩餘定理，方程組

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

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

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

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

公式的證明

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

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

例子

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

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

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

其中的d為n的正約數。

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

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

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

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

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

即歐拉定理。

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

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

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

即費馬小定理。

歐拉商數

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

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

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

其中C = 0.8178146...。^[7]

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

${\displaystyle {\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成比例。^[8]

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

Ford定理

Ford (1999) harvtxt模板錯誤: 無指向目標: CITEREFFord1999 (幫助)證明說對於任意整數k ≥ 2而言，總存在一個歐拉商數m，其重複度為k，也就是說總有數字使得這等式φ(n) = m有剛好k個解。這結果由瓦茨瓦夫·謝爾賓斯基所猜測，^[11]且是Schinzel猜想H（英語：Schinzel's hypothesis H）的一個結果。^[7]事實上，對於任何出現的重複度而言，該重複度會出現無限多次。^[7][10]

然而，沒有任何數字m的重複度為k = 1。卡邁克爾猜想的歐拉函數猜想（英語：Carmichael's totient function conjecture）講的是沒有m的重複度為k = 1。^[12]

完全歐拉商數

主條目：完全歐拉商數

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

生成函數

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

由${\displaystyle \varphi }$(n)生成的狄利克雷級數是：

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

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

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

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

${\displaystyle .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\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}}}}$

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

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

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

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

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

推導如下：

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

後者等價於：

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

歐拉函數的走勢

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

在n足夠大時，有估計：

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

如果考慮比值：

${\displaystyle \,\varphi (n)/n,}$

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

${\displaystyle C\,\log \log n/\log n.}$

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

${\displaystyle {\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趨於無窮大時，它們互質的概率趨於 ${\displaystyle 6/\pi ^{2}}$ 。一個相關的結果是比值${\displaystyle \varphi (n)/n}$的平均值：

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

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

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

與歐拉函數有關的不等式

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

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

未解決問題

萊默的歐拉函數問題

主條目：萊默的歐拉函數問題

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

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

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

主條目：卡邁克爾猜想的歐拉函數猜想

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

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

黎曼猜想

黎曼猜想成立，當且僅當以下不等式對所有的n ≥ p₁₂₀₅₆₉#成立。此處的p₁₂₀₅₆₉#是最初的120569個質數的乘積：

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

此處的γ是歐拉常數。^[17]

程式代碼

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

文獻來源

參考資料

1. Where does the word “totient” come from?. [2014-10-16]. （原始內容存檔於2014-10-12）.
2. Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608
3. Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814
4. Guy (2004) p.144
5. Sándor & Crstici (2004) p.230
6. Zhang, Mingzhi. On nontotients. Journal of Number Theory. 1993, 43 (2): 168–172. ISSN 0022-314X. Zbl 0772.11001. doi:10.1006/jnth.1993.1014 .
7. Ford, Kevin. The distribution of totients. Ramanujan J. Developments in Mathematics. 1998, 2 (1–2): 67–151. ISBN 978-1-4419-5058-1. ISSN 1382-4090. Zbl 0914.11053. arXiv:1104.3264 . doi:10.1007/978-1-4757-4507-8_8.
8. Sándor et al (2006) p.22
9. Sándor et al (2006) p.21
10. Guy (2004) p.145
11. Sándor & Crstici (2004) p.229
12. Sándor & Crstici (2004) p.228
13. Ribenboim, pp. 36–37.
14. Cohen, Graeme L.; Hagis, Peter Jr. On the number of prime factors of n if φ(n) divides n − 1. Nieuw Arch. Wiskd. III Series. 1980, 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.
15. Hagis, Peter Jr. On the equation M·φ(n) = n − 1. Nieuw Arch. Wiskd. IV Series. 1988, 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.
16. Guy (2004) p.142
17. Broughan, Kevin. Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents First. Cambridge University Press. 2017. ISBN 978-1-107-19704-6. Corollary 5.35