欧拉函数
在數論中,對正整數n,歐拉函數是小於等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名,它又稱為φ函數(由高斯所命名)或是歐拉總計函數[1](totient function,由西爾維斯特所命名)。
例如,因為1,3,5,7均和8互質。
欧拉函数实际上是模n的同余类所构成的乘法群(即环的所有单位元组成的乘法群)的阶。这个性质与拉格朗日定理一起構成了欧拉定理的證明。
歷史:欧拉函數與費馬小定理编辑
- 假若 為質數, 為任意正整數,那麼 可被 整除。
然後欧拉予以一般化:
- 假若 與 互質,那麼 可被 整除。亦即, 。
其中 即為歐拉總計函數。如果 為質數,那麼 ,因此,有高斯的版本[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趋于无穷大时,它们互质的概率趋于 。一个相关的结果是比值 的平均值:
其他与欧拉函数有关的等式编辑
- 使得
- 使得
与欧拉函数有关的不等式编辑
程式代码编辑
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
文獻来源编辑
參考資料编辑
- ^ Where does the word “totient” come from?. [2014-10-16]. (原始内容存档于2014-10-12).
- ^ Mathematical Thought From Ancient to Modern Times, 第 2 卷,p.608
- ^ Mathematical Thought From Ancient to Modern Times, 第 3 卷,p.814