欧拉函数

小於或等於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