在数论中,对正整数n,欧拉函数是小于等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数[1](totient function,由西尔维斯特所命名)。
例如,因为1、3、5和7均与8互质。
欧拉函数实际上是模n的同余类所构成的乘法群(即环的所有单位元组成的乘法群)的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。
历史:欧拉函数与费马小定理
- 假若 为质数, 为任意正整数,那么 可被 整除。
然后欧拉予以一般化:
- 假若 与 互质,那么 可被 整除。亦即,。
其中 即为欧拉总计函数。如果 为质数,那么 ,因此,有高斯的版本[3]:
- 假若 为质数, 与 互质( 不是 的倍数),那么 。
欧拉函数的值
以下为 为至时,对应 的值
+ | 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本身)。
欧拉函数是积性函数,即是说若m,n互质,则。使用中国剩余定理有较简略的证明:设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,和可建立双射(一一对应)关系,因此两者元素个数相等。
较详细的证明如下:
设,且。若与互质,则与、均互质。又因为,若分别与互质,则一定和互质。反之亦然,即若与互质,则亦有分别与互质。
由中国剩余定理,方程组
的通解可以写成 其中为固定的整数,故二元组(要满足)与小于且与互质的正整数一一对应。
由的定义(和乘法原理),前一种数对的个数为。而后一种数的个数为。
所以,
结合以上两小节的结果可得:若有质因数分解式,则
计算的欧拉函数值:
性质
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)指的是欧拉函数的值,也就是说,若m是一个欧拉商数,那至少存在一个n,使得φ(n) = m。而欧拉商数m的“重复度”(valency或multiplicity),指的是这等式的解数。[4]相对地,一个非欧拉商数指的是不是欧拉商数的自然数。显然所有大于1的奇数都是非欧拉商数,此外也存有无限多的偶数是非欧拉商数,[5]且所有的正整数都有一个倍数是非欧拉商数。[6]
不大于x的欧拉商数个数可由以下公式给出:
其中C = 0.8178146...。[7]
考虑重复度,那么不大于x的欧拉商数个数可由以下公式给出:
其中对任意正数k而言,误差项R至多与x/(log x)k成比例。[8]
Ford (1999) 证明说对于任意整数k ≥ 2而言,总存在一个欧拉商数m,其重复度为k,也就是说总有数字使得这等式φ(n) = m有刚好k个解。这结果由瓦茨瓦夫·谢尔宾斯基所猜测,[11]且是Schinzel猜想H的一个结果。[7]事实上,对于任何出现的重复度而言,该重复度会出现无限多次。[7][10]
然而,没有任何数字m的重复度为k = 1。卡迈克尔猜想的欧拉函数猜想讲的是没有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趋于无穷大时,它们互质的概率趋于 。一个相关的结果是比值的平均值:
其他与欧拉函数有关的等式
- 使得
- 使得
与欧拉函数有关的不等式
未解决问题
若p是质数,则有φ(p) = p − 1。1932年,德里克·亨利·莱默问说是否有合成数n使得φ(n) 整除n − 1。目前未知是否有这样的数存在。[13]
1933年莱默证明说若有这样的,那么必然是奇数、必然是无平方因子数,且必然有至少七个不同的质因数()。1980年,Cohen和Hagis证明了说,若这样的存在,则且有至少14个不同的质因数();[14]此外,Hagis证明了说若这样的存在且可被3除尽,那么且有至少298848个不同的质因数()。[15][16]
此猜想认为说不存在正整数n,使得对于所有其他的m而言,在m ≠ n的状况下必有φ(m) ≠ φ(n)。可见上述Ford定理一节的说明。
若有一个如此的反例存在,就必有无限多的反例存在,而最小的可能反例,在十进制下,其位数超过一百亿。[4]
黎曼猜想成立,当且仅当以下不等式对所有的n ≥ p120569#成立。此处的p120569#是最初的120569个质数的乘积:
程式代码
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
文献来源
参考资料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.