歐拉函數(shù)（Euler function），也稱(chēng)為φ函數(shù)或歐拉總計(jì)函數(shù)（totient function），是數(shù)論中的一個(gè)重要函數(shù)，表示所有不超過(guò)正整數(shù)n，且與n互素的正整數(shù)的個(gè)數(shù)。
1760年，瑞士數(shù)學(xué)家萊昂哈德·歐拉（Leonhard Euler）證明了費(fèi)馬定理，同年，提出了關(guān)于表示所有不大于n且與n互素的正整數(shù)個(gè)數(shù)的問(wèn)題。1770年，柏林出版社出版了歐拉的數(shù)論專(zhuān)著《代數(shù)指南》(Anleitung zur algebra)，該函數(shù)被收入書(shū)中。1801年，高斯(Gauss)將其命名為歐拉函數(shù)。
歐拉函數(shù)有一些基本性質(zhì)，如歐拉函數(shù)是積性函數(shù)，但不是完全積性函數(shù)。與其相關(guān)的概念是簡(jiǎn)化剩余系，歐拉定理是費(fèi)馬小定理對(duì)于歐拉函數(shù)的推廣。歐拉函數(shù)在數(shù)論、加密學(xué)方面應(yīng)用廣泛，如RSA算法是按照歐拉函數(shù)性質(zhì)設(shè)計(jì)而來(lái)。
這個(gè)函數(shù)不僅在數(shù)論中有著重要的地位，也在現(xiàn)代密碼學(xué)中扮演著關(guān)鍵角色，尤其是在RSA加密算法的設(shè)計(jì)中。歐拉函數(shù)實(shí)際上是模n的同余類(lèi)所構(gòu)成的乘法群的階，這個(gè)性質(zhì)與拉格朗日定理一起構(gòu)成了歐拉定理的證明基礎(chǔ)。
歷史
背景與命名
歐拉猜想的提出可追溯至18世紀(jì)。1760年，長(zhǎng)城歐拉證明了費(fèi)馬定理，同年，他提出了關(guān)于表示所有不大于且與互素的正整數(shù)個(gè)數(shù)的問(wèn)題，并引入了一個(gè)函數(shù)用于表示它們的關(guān)系。1770年，柏林出版社出版了歐拉的數(shù)論專(zhuān)著《代數(shù)指南》(Anleitung zur algebra)，該函數(shù)被收入書(shū)中。1801年，數(shù)學(xué)家高斯(Gauss)在他的《算術(shù)研究》一書(shū)中證明了，并將命名為歐拉函數(shù)。1879年，詹姆斯·約瑟夫·西爾維斯特（J. J. Sylvester）為該函數(shù)創(chuàng)造了術(shù)語(yǔ)totient。
發(fā)展與突破
關(guān)于歐拉函數(shù)，許多學(xué)者在后續(xù)提出了許多猜想與討論。1932年，萊默(Lehmer,D.H.)提出猜想：不存在復(fù)合數(shù)，使得，這個(gè)猜想至今尚未解決。1983年，美國(guó)學(xué)者克羅斯（Cross J T）將歐拉函數(shù)域代數(shù)中的環(huán)論相結(jié)合，研究了整數(shù)環(huán)上的歐拉函數(shù)。
定義
歐拉函數(shù)是重要的數(shù)論函數(shù)之一。歐拉函數(shù)表示所有不超過(guò)正整數(shù)，且與互素的正整數(shù)的個(gè)數(shù)。若，，，等，為了計(jì)算需要，規(guī)定。如果自然數(shù)的標(biāo)準(zhǔn)分解式為，則或，特別地，當(dāng)為素?cái)?shù)時(shí)，有，。
相關(guān)概念
簡(jiǎn)化剩余系
設(shè)為一正整數(shù)，在模的所有不同簡(jiǎn)化剩余類(lèi)中，從每個(gè)類(lèi)任取一個(gè)數(shù)組成的整數(shù)的集合，叫模的一個(gè)簡(jiǎn)化剩余系。歐拉函數(shù)簡(jiǎn)化剩余系定義為：設(shè)為一正整數(shù)，，且，則是模的一個(gè)簡(jiǎn)化剩余系。
積性函數(shù)
設(shè)是定義在集合上的整數(shù)的函數(shù)，并滿足當(dāng)，時(shí)，有，則稱(chēng)為積性函數(shù)。
性質(zhì)
性質(zhì)1
歐拉函數(shù)是積性函數(shù)，但不是完全積性函數(shù)。
證明：因?yàn)椋O(shè)是互素的正整數(shù)。若或，則有。設(shè)，分別是的標(biāo)準(zhǔn)分解式。由于互素，故的標(biāo)準(zhǔn)分解式為
。又因?yàn)椋允欠e性函數(shù)，歐拉函數(shù)是積性函數(shù)。
性質(zhì)2
設(shè)，則。
證明：首先，對(duì)任意素?cái)?shù)，有當(dāng)且僅當(dāng)，和或，根據(jù)歐拉函數(shù)是積性函數(shù)得
。
性質(zhì)3
設(shè)為大于的整數(shù)且其標(biāo)準(zhǔn)分解式為，則。
證明：根據(jù)其他性質(zhì)可知是積性函數(shù)，可通過(guò)如下性質(zhì)證明。
根據(jù)是積性函數(shù)，為大于的整數(shù)且其標(biāo)準(zhǔn)分解式為，則。令，根據(jù)若是素?cái)?shù)，是正整數(shù)，則，可，得到。
性質(zhì)4
設(shè)為大于的整數(shù)且其標(biāo)準(zhǔn)分解式為，則
性質(zhì)5
用表示不超過(guò)整數(shù)且與互素的正整數(shù)（共）之和。
設(shè)，則。
證明：如果，那么。設(shè)，則，，從而有。，即，所以。設(shè)為不超過(guò)且與互素的正整數(shù)的全體，則
也是不超過(guò)且與互素的正整數(shù)的全體。于是
，。把兩個(gè)式子加在一起得，即。
性質(zhì)6
如果整數(shù)，則。
性質(zhì)7
如果整數(shù)，則。
相關(guān)定理
歐拉-費(fèi)馬定理
設(shè)，則有，當(dāng)為素?cái)?shù)時(shí)，對(duì)任意有。通常將稱(chēng)為費(fèi)馬小定理，稱(chēng)為歐拉定理，因此，歐拉定理是費(fèi)馬小定理對(duì)于歐拉函數(shù)的推廣。
證明：該定理的證明需要引入如下定理：，那么遍歷模的簡(jiǎn)化剩余系的充分必要條件是遍歷模的簡(jiǎn)化剩余系。也就是說(shuō)，是模的簡(jiǎn)化剩余系的充分必要條件是是模的簡(jiǎn)化剩余系。因此，取是模的一個(gè)既約剩余系，由以上定理可得，當(dāng)時(shí)，是模的一個(gè)既約剩余系。由知，。由于，利用自然數(shù)與整數(shù)性質(zhì)，得費(fèi)馬小定理，當(dāng)為素?cái)?shù)時(shí)，由費(fèi)馬小定理和，得到，。因此，對(duì)任意有。
非歐拉商數(shù)
非歐拉商數(shù)
不屬于歐拉函數(shù)值域的偶數(shù)，即如果一個(gè)正偶數(shù)所對(duì)應(yīng)的歐拉方程無(wú)解，那么這個(gè)數(shù)稱(chēng)為非歐拉商數(shù)。
結(jié)論與構(gòu)造方法
所有能被整除，但不能被整除的非歐拉商數(shù)，都可以用通式表出，其中為奇素?cái)?shù)，為正整數(shù)。
構(gòu)造以下非歐拉商數(shù)：
其中。
前面一個(gè)數(shù)可以表示為的素?cái)?shù)減去，如，后面一個(gè)數(shù)是取這個(gè)素?cái)?shù)的整數(shù)倍加，且加后得到的數(shù)應(yīng)為素?cái)?shù)，也就是，其中，令要求為素?cái)?shù)。
廣義歐拉函數(shù)
給定正整數(shù)和，關(guān)于的廣義歐拉函數(shù)定義為，即等于不超過(guò)且與互質(zhì)的正整數(shù)的個(gè)數(shù)，這里表示不超過(guò)的最大整數(shù)。
由此定義易證明，其中為莫比烏斯函數(shù)（M?bius），即當(dāng)為不同的素?cái)?shù)，時(shí)，
該函數(shù)有一些與歐拉函數(shù)相似的基本性質(zhì)，如，且。同時(shí)，它還存在如下特殊結(jié)論。
結(jié)論1：若，為正整數(shù)，且，則特別地，當(dāng)時(shí)，。
結(jié)論2：若為正整數(shù)，且，則。
應(yīng)用
數(shù)學(xué)
歐拉函數(shù)在數(shù)論中可以用于著名猜想的證明，如哥德巴赫猜想。基本思想是，對(duì)于任意給定的自然數(shù)n，按大小順序把比它小的自然數(shù)列出，劃掉比它小的2的倍數(shù)，再剩下數(shù)中劃掉3的倍數(shù)，一直做下去，直到所有合數(shù)被劃掉。歐拉函數(shù)給出了一種特殊情形的篩法，可以對(duì)任意連續(xù)的自然數(shù)段進(jìn)行篩選，或者對(duì)等差數(shù)列中任意連續(xù)的自然數(shù)段進(jìn)行篩除，可快速解決諸多素?cái)?shù)問(wèn)題。比如利用歐拉函數(shù)證明素?cái)?shù)有無(wú)窮個(gè)。
證明：設(shè)所有不同的素?cái)?shù)為，并記。設(shè)，若，則必有素?cái)?shù)使得，但是所有素?cái)?shù)之積，故也有，這表明與不互素。于是中與互素的僅有，從而。另一方面，根據(jù)性質(zhì)6得到，矛盾，證明完畢。
加密學(xué)
密碼學(xué)是用來(lái)保護(hù)信息安全的一種必要手段，其中RSA算法是主流的公鑰加密算法之一，它的算法是以歐拉函數(shù)的性質(zhì)設(shè)計(jì)而來(lái)，該算法基于數(shù)論事實(shí)是：計(jì)算兩個(gè)大素?cái)?shù)的乘積是簡(jiǎn)單的，但是要將這個(gè)乘積進(jìn)行因式分解是很難的。所以RSA算法中將兩個(gè)大素?cái)?shù)的乘積作為公鑰進(jìn)行公開(kāi)，而這兩個(gè)大素?cái)?shù)則用來(lái)獲取私鑰，私鑰是保密的。因此，RSA加密算法中，要用到素?cái)?shù)、互素?cái)?shù)、模運(yùn)算以及歐拉函數(shù)等數(shù)學(xué)知識(shí)。
未解決問(wèn)題
萊默的歐拉函數(shù)問(wèn)題
萊默的歐拉函數(shù)問(wèn)題是數(shù)論中的一個(gè)未解決問(wèn)題，它詢(xún)問(wèn)是否存在合成數(shù)n使得φ(n)整除n - 1。目前已知如果這樣的n存在，它必須是奇數(shù)、無(wú)平方因子數(shù)，并且有至少七個(gè)不同的質(zhì)因數(shù)。
卡邁克爾猜想的歐拉函數(shù)猜想
卡邁克爾猜想的歐拉函數(shù)猜想認(rèn)為不存在正整數(shù)n，使得對(duì)于所有其他的m而言，在m ≠ n的情況下必有φ(m) ≠ φ(n)。如果存在這樣的反例，那么必然有無(wú)限多的反例存在。
黎曼猜想
黎曼猜想與歐拉函數(shù)有著密切的聯(lián)系。黎曼猜想成立的一個(gè)必要條件是存在一個(gè)與n相關(guān)的不等式，涉及到歐拉函數(shù)值與n的比值。
程式代碼
C++
```cpp
template
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;
}
```
參考資料 >