打开主菜单
n为1至1000的整数时的值

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

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

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

歷史:欧拉函數與費馬小定理编辑

1736年,欧拉證明了费马小定理[2]

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

然後欧拉予以一般化:

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

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

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

欧拉函數的值编辑

 (小于等于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時,此式則為:

 

費馬小定理

生成函数编辑

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

 (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,则有:
 

参考来源编辑

  • 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?
  2. ^ Mathematical Thought From Ancient to Modern Times, 第 2 卷,p.608
  3. ^ Mathematical Thought From Ancient to Modern Times, 第 3 卷,p.814