歐拉函數

小於或等於n的正整數中與n互質的數的數目

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

n為1至1000的整數時的值

例如,因為1、3、5和7均與8互質

歐拉函數實際上是模n同餘類所構成的乘法(即環的所有單位元組成的乘法群)的。這個性質與拉格朗日定理一起構成了歐拉定理的證明。

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

編輯

1736年,歐拉證明了費馬小定理[2]

假若   為質數,  為任意正整數,那麼   可被   整除。

然後歐拉予以一般化:

假若    互質,那麼   可被   整除。亦即, 

其中   即為歐拉總計函數。如果   為質數,那麼  ,因此,有高斯的版本[3]

假若   為質數,   互質(  不是   的倍數),那麼  

歐拉函數的值

編輯

以下為   時,對應  的值

φ(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

 標準分解 (其中各 為互異的質因子,各 為質因子的次數),則歐拉函數在該處的值為

 

亦可等價地寫成

 

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

質數冪處取值

編輯

最簡單的情況有 (小於等於1的正整數中唯一和1互質的數就是1本身)。

一般地,若n質數pk,則 ,因為除了p倍數外,其他數都跟n互質。

積性

編輯

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

較詳細的證明如下:

 ,且 。若  互質,則   均互質。又因為 ,若 分別與 互質,則 一定和 互質。反之亦然,即若  互質,則亦有 分別與 互質。

中國剩餘定理,方程組

 

的通解可以寫成  其中 為固定的整數,故二元組 (要滿足 )與小於 且與 互質的正整數 一一對應。

 的定義(和乘法原理),前一種數對 的個數為 。而後一種數 的個數為 

所以, 

公式的證明

編輯

結合以上兩小節的結果可得:若 質因數分解式 ,則

 

例子

編輯

計算 的歐拉函數值:

 

性質

編輯

n的歐拉函數  也是循環群 Cn生成元的個數(也是n分圓多項式的次數)。Cn 中每個元素都能生成 Cn 的一個子群,即必然是某個子群的生成元。而且按照定義,不同的子群不可能有相同的生成元。此外, Cn 的所有子群都具有 Cd 的形式,其中d整除n(記作d | n)。因此只要考察n的所有因數d,將 Cd 的生成元個數相加,就將得到 Cn 的元素總個數:n。也就是說:

 

其中的dn的正約數。

運用默比烏斯反轉公式來「翻轉」這個和,就可以得到另一個關於 的公式:

 

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

對任何兩個互質的正整數a, m(即 gcd(a,m) = 1), ,有

 

歐拉定理

這個定理可以由群論中的拉格朗日定理得出,因為任意與m互質的a都屬於環   的單位元組成的乘法群 

m質數p時,此式則為:

 

費馬小定理

歐拉商數

編輯

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

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

 

其中C = 0.8178146...[7]

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

 

其中對任意正數k而言,誤差項R至多與x/(log x)k成比例。[8]

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

Ford定理

編輯

Ford (1999)證明說對於任意整數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)是一個等同於其歐拉函數迭代總和的整數,也就是說,如果將歐拉函數套用在一個正整數 之後,並將歐拉函數套用在如此所得的結果上,如此下去,直到最後得到1為止,並將這一系列的數給加總起來。若這總和為 ,那麼 就是一個完全歐拉商數。

生成函數

編輯

以下兩個由歐拉函數生成的級數都是來自於上節所給出的性質: 

 (n)生成的狄利克雷級數是:

 

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

 
 
 
使用開始時的等式,就得到: 
於是 

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

 

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

推導如下:

 

後者等價於:

 

歐拉函數的走勢

編輯

隨着n變大,估計  的值是一件很難的事。當n為質數時, ,但有時 又與n差得很遠。

n足夠大時,有估計:

對每個 ε > 0,都有n > N(ε)使得  

如果考慮比值:

 

由以上已經提到的公式,可以得到其值等於類似 的項的乘積。因此,使比值小的n將是兩兩不同的質數的乘積。由素數定理可以知道,常數 ε 可以被替換為:

 

 就平均值的意義上來說是與n很相近的,因為:

 

其中的O表示大O符號。這個等式也可以說明在集合 {1, 2, ..., n} 中隨機選取兩個數,則當n趨於無窮大時,它們互質的概率趨於   。一個相關的結果是比值 的平均值:

 

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

編輯
  1.  
  2.   使得  
  3.   使得  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  

與歐拉函數有關的不等式

編輯
  1.  ,其中n > 2,γ 為歐拉-馬歇羅尼常數
  2.   ,其中n > 0。
  3. 對整數n > 6, 
  4. n為質數時,顯然有 。對於合數n,則有:
 

未解決問題

編輯

萊默的歐拉函數問題

編輯

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

1933年萊默證明說若有這樣的 ,那麼 必然是奇數、必然是無平方因子數,且必然有至少七個不同的質因數( )。1980年,Cohen和Hagis證明了說,若這樣的 存在,則  有至少14個不同的質因數( );[14]此外,Hagis證明了說若這樣的 存在且可被3除盡,那麼  有至少298848個不同的質因數( )。[15][16]

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

編輯

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

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

黎曼猜想

編輯

黎曼猜想成立,當且僅當以下不等式對所有的np120569#成立。此處的p120569#是最初的120569質數的乘積

 

此處的γ歐拉常數[17]

程式代碼

編輯
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頁.
  • 柯召,孫琦:數論講義(上冊),第二版,高等教育出版社,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. ^ 4.0 4.1 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. ^ 7.0 7.1 7.2 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. ^ 10.0 10.1 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