欧拉函数

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

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

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

 歷史：欧拉函數與費馬小定理 
1736年，欧拉證明了费马小定理Mathematical Thought From Ancient to Modern Times, 第 2 卷，p.608：
假若  為質數， 為任意正整數，那麼  可被  整除。
然後欧拉予以一般化：
假若  與  互質，那麼  可被  整除。亦即，。
其中  即為歐拉總計函數。如果  為質數，那麼 ，因此，有高斯的版本Mathematical Thought From Ancient to Modern Times, 第 3 卷，p.814：
假若  為質數， 與  互質（ 不是  的倍數），那麼 。

 欧拉函數的值 

以下為 為至時，對應 的值
{| class="wikitable" style="text-align: right"
|+ for 
! +
! 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是質數p的k次冪，則，因為除了p的倍數外，其他數都跟n互質。

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

較詳細的證明如下：

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

由中國剩餘定理，方程組

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

由的定義（和乘法原理），前一種數對的個數為。而後一種數的個數為。

所以，

公式的證明
結合以上兩小節的結果可得：若有質因數分解式，則

-{zh-hant:
;
zh-hans:
;
}-

例子
計算的歐拉函數值：

 性质 
n的欧拉函数 也是循环群 Cn 的生成元的个数（也是n阶分圆多项式的次数）。Cn 中每个元素都能生成 Cn 的一个子群，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， Cn 的所有子群都具有 Cd 的形式，其中d整除n（记作d | n）。因此只要考察n的所有因数d，将 Cd 的生成元个数相加，就将得到 Cn 的元素总个数：n。也就是说：

其中的d为n的正约数。

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

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

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

即欧拉定理。

这个定理可以由群论中的拉格朗日定理得出，因为任意与m互质的a都属于环  的单位元组成的乘法群

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

即費馬小定理。

歐拉商數
歐拉商數（totient number）指的是歐拉函數的值，也就是說，若是一個歐拉商數，那至少存在一個，使得。而歐拉商數的「重複度」（valency或multiplicity），指的是這等式的解數。Guy (2004) p.144相對地，一個非歐拉商數指的是不是歐拉商數的自然數。顯然所有大於1的奇數都是非歐拉商數，此外也存有無限多的偶數是非歐拉商數，Sándor & Crstici (2004) p.230且所有的正整數都有一個倍數是非歐拉商數。

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

其中。

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

其中對任意正數而言，誤差項至多與成比例。Sándor et al (2006) p.22

目前已知對於任意的而言，有無限多個，其重複度超過。Sándor et al (2006) p.21Guy (2004) p.145

Ford定理
證明說對於任意整數而言，總存在一個歐拉商數，其重複度為，也就是說總有數字使得這等式有剛好個解。這結果由瓦茨瓦夫·謝爾賓斯基所猜測，Sándor & Crstici (2004) p.229且是的一個結果。事實上，對於任何出現的重複度而言，該重複度會出現無限多次。

然而，沒有任何數字的重複度為。講的是沒有的重複度為。Sándor & Crstici (2004) p.228

完全歐拉商數

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

 生成函数 

以下两个由欧拉函数生成的级数都是来自于上节所给出的性质：。

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

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

使用开始时的等式，就得到：
于是

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



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

推导如下：

后者等价于：

 欧拉函数的走势 
随着n变大，估计 的值是一件很难的事。当n为质数时，，但有时又与n差得很远。

在n足够大时，有估计：
对每个 ε > 0，都有n > N(ε)使得 

如果考虑比值：

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

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

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

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


  使得 
  使得 







 与欧拉函数有关的不等式 
 ，其中n > 2，γ 为欧拉-马歇罗尼常数。
  ，其中n > 0。
 对整数n > 6，。
 当n为质数时，显然有。对于合数的n，则有：

 未解決問題 
 萊默的歐拉函數問題 

若是質數，則有。1932年，德里克·亨利·萊默問說是否有合成數使得整除。目前未知是否有這樣的數存在。Ribenboim, pp. 36–37.

1933年萊默證明說若有這樣的，那麼必然是奇數、必然是無平方因子數，且必然有至少七個不同的質因數（）。1980年，Cohen和Hagis證明了說，若這樣的存在，則且有至少14個不同的質因數（）；此外，Hagis證明了說若這樣的存在且可被3除盡，那麼且有至少298848個不同的質因數（）。Guy (2004) p.142

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

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

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

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

此處的是歐拉常數。 Corollary 5.35

程式代码

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
 文獻来源 

 參考資料 

Category:同余
Category:积性函数
Category:包含证明的条目
Category:代数
Category:数论
Category:莱昂哈德·欧拉