此条目的主题是小于等于
n的正整数中与
n互质的数的数目。关于形式为

的函数,请见“
欧拉函数 (复变函数)”。
当
n为1至1000的整数时

的值
在数论中,对正整数n,欧拉函数
是小于等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数(由高斯所命名)或是欧拉总计函数[1](totient function,由西尔维斯特所命名)。
例如
,因为1,3,5,7均和8互质。
欧拉函数实际上是模n的同余类所构成的乘法群(即环
的所有单位元组成的乘法群)的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。
历史:欧拉函数与费马小定理[编辑]
1736年,欧拉证明了费马小定理[2]:
- 假若
为质数,
为任意正整数,那么
可被
整除。
然后欧拉予以一般化:
- 假若
与
互质,那么
可被
整除。亦即,
。
其中
即为欧拉总计函数。如果
为质数,那么
,因此,有高斯的版本[3]:
- 假若
为质数,
与
互质(
不是
的倍数),那么
。
欧拉函数的值[编辑]
若
有标准分解
(其中各
为互异的质因子,各
为质因子的次数),则欧拉函数在该处的值为

亦可等价地写成

此结果可由
在质数幂处的取值,以及其积性得到。
质数幂处取值[编辑]
最简单的情况有
(小于等于1的正整数中唯一和1互质的数就是1本身)。
一般地,若n是质数p的k次幂,则
,因为除了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。也就是说:

其中的d为n的正约数。
运用默比乌斯反转公式来“翻转”这个和,就可以得到另一个关于
的公式:

其中 μ 是所谓的默比乌斯函数,定义在正整数上。
对任何两个互质的正整数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趋于无穷大时,它们互质的概率趋于
。一个相关的结果是比值
的平均值:

其他与欧拉函数有关的等式[编辑]

使得 ![{\displaystyle [(a>1\land n>1)\rightarrow (l|\varphi (a^{n}-1)\land l\geq n)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/580703fbafb9bc0f881425b2a65ce95e2c98eeb7)
使得 ![{\displaystyle [(a>1\land n>6\land 4\nmid n)\rightarrow (l|\varphi (a^{n}-1)\land l\geq 2n)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7f52bf7a4c789d0247a5b71dd96b059946233fa)






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

程式代码[编辑]
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页.
- 柯召,孙琦:数论讲义(上册),第二版,高等教育出版社,2001
文献来源[编辑]
参考资料[编辑]