fbpx
维基百科

欧拉函数

數論中,對正整數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時,此式則為:

 

費馬小定理

生成函数 编辑

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

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

程式代码 编辑

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页.
  • Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311. (页面存档备份,存于互联网档案馆
  • 柯召,孙琦:数论讲义(上册),第二版,高等教育出版社,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

欧拉函数, 此条目的主題是小於等於n的正整數中與n互質的數的數目, 关于形式為ϕ, displaystyle, prod, infty, 的函數, 請見, 歐拉函數, 複變函數, 在數論中, 對正整數n, 歐拉函數φ, displaystyle, varphi, 是小於等於n的正整數中與n互質的數的數目, 此函數以其首名研究者歐拉命名, 它又稱為φ函數, 由高斯所命名, 或是歐拉總計函數, totient, function, 由西爾維斯特所命名, 当n为1至1000的整数时φ, displaystyle, var. 此条目的主題是小於等於n的正整數中與n互質的數的數目 关于形式為ϕ q k 1 1 q k displaystyle phi q prod k 1 infty 1 q k 的函數 請見 歐拉函數 複變函數 在數論中 對正整數n 歐拉函數f n displaystyle varphi n 是小於等於n的正整數中與n互質的數的數目 此函數以其首名研究者歐拉命名 它又稱為f函數 由高斯所命名 或是歐拉總計函數 1 totient function 由西爾維斯特所命名 当n为1至1000的整数时f n displaystyle varphi n 的值例如f 8 4 displaystyle varphi left 8 right 4 因為1 3 5和7均與8互質 欧拉函数实际上是模n的同余类所构成的乘法群 即环Z n Z displaystyle mathbb Z n mathbb Z 的所有单位元组成的乘法群 的阶 这个性质与拉格朗日定理一起構成了欧拉定理的證明 目录 1 歷史 欧拉函數與費馬小定理 2 欧拉函數的值 2 1 質數冪處取值 2 2 積性 2 3 公式的證明 2 4 例子 3 性质 4 生成函数 5 欧拉函数的走势 6 其他与欧拉函数有关的等式 7 与欧拉函数有关的不等式 8 程式代码 8 1 C 9 参考来源 10 文獻来源 11 參考資料歷史 欧拉函數與費馬小定理 编辑1736年 欧拉證明了费马小定理 2 假若 p displaystyle p nbsp 為質數 a displaystyle a nbsp 為任意正整數 那麼 a p a displaystyle a p a nbsp 可被 p displaystyle p nbsp 整除 然後欧拉予以一般化 假若 a displaystyle a nbsp 與 n displaystyle n nbsp 互質 那麼 a f n 1 displaystyle a varphi n 1 nbsp 可被 n displaystyle n nbsp 整除 亦即 a f n 1 mod n displaystyle a varphi n equiv 1 pmod n nbsp 其中 f n displaystyle varphi n nbsp 即為歐拉總計函數 如果 n displaystyle n nbsp 為質數 那麼 f n n 1 displaystyle varphi n n 1 nbsp 因此 有高斯的版本 3 假若 p displaystyle p nbsp 為質數 a displaystyle a nbsp 與 p displaystyle p nbsp 互質 a displaystyle a nbsp 不是 p displaystyle p nbsp 的倍數 那麼 a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p nbsp 欧拉函數的值 编辑以下為n displaystyle n nbsp 為1 displaystyle 1 nbsp 至100 displaystyle 100 nbsp 時 對應f n displaystyle varphi n nbsp 的值 f n for 1 n 100 1 2 3 4 5 6 7 8 9 100 1 1 2 2 4 2 6 4 6 410 10 4 12 6 8 8 16 6 18 820 12 10 22 8 20 12 18 12 28 830 30 16 20 16 24 12 36 18 24 1640 40 12 42 20 24 22 46 16 42 2050 32 24 52 18 40 24 36 28 58 1660 60 30 36 32 48 20 66 32 44 2470 70 24 72 36 40 36 60 24 78 3280 54 40 82 24 64 42 56 40 88 2490 72 44 60 46 72 32 96 42 60 40若n displaystyle n nbsp 有標準分解p 1 k 1 p 2 k 2 p r k r displaystyle p 1 k 1 p 2 k 2 cdots p r k r nbsp 其中各p i displaystyle p i nbsp 為互異的質因子 各k i 1 displaystyle k i geq 1 nbsp 為質因子的次數 則歐拉函數在該處的值為 f n p 1 k 1 1 p 2 k 2 1 p r k r 1 p 1 1 p 2 1 p r 1 displaystyle varphi n p 1 k 1 1 p 2 k 2 1 cdots p r k r 1 p 1 1 p 2 1 cdots p r 1 nbsp 亦可等價地寫成 f n n 1 1 p 1 1 1 p 2 1 1 p r displaystyle varphi n n left 1 frac 1 p 1 right left 1 frac 1 p 2 right cdots left 1 frac 1 p r right nbsp 此結果可由f displaystyle varphi nbsp 在質數冪處的取值 以及其積性得到 質數冪處取值 编辑 最簡單的情況有f 1 1 displaystyle varphi 1 1 nbsp 小于等于1的正整数中唯一和1互質的數就是1本身 一般地 若n是質數p的k次冪 則f n f p k p k p k 1 p 1 p k 1 displaystyle varphi n varphi p k p k p k 1 p 1 p k 1 nbsp 因為除了p的倍數外 其他數都跟n互質 積性 编辑 歐拉函數是積性函數 即是说若m n互質 則f m n f m f n displaystyle varphi mn varphi m varphi n nbsp 使用中國剩餘定理有較簡略的證明 設A B C是跟m n mn互質的數的集 據中國剩餘定理 A B displaystyle A times B nbsp 和C displaystyle C nbsp 可建立雙射 一一對應 關係 因此兩者元素個數相等 較詳細的證明如下 設N lt m n displaystyle N lt mn nbsp 且N k 1 m p k 2 n q displaystyle N k 1 m p k 2 n q nbsp 若N displaystyle N nbsp 與m n displaystyle mn nbsp 互質 則N displaystyle N nbsp 與m displaystyle m nbsp n displaystyle n nbsp 均互質 又因為 k 1 m p m p m k 2 n q n q n displaystyle k 1 m p m p m k 2 n q n q n nbsp 若p q displaystyle p q nbsp 分別與m n displaystyle m n nbsp 互質 則N displaystyle N nbsp 一定和m n displaystyle mn nbsp 互質 反之亦然 即若N displaystyle N nbsp 與m n displaystyle mn nbsp 互質 則亦有p q displaystyle p q nbsp 分別與m n displaystyle m n nbsp 互質 由中國剩餘定理 方程組 N p mod m N q mod n displaystyle left begin matrix N equiv p pmod m N equiv q pmod n end matrix right nbsp 的通解可以寫成N k m n p t 1 m q t 2 n k Z displaystyle N kmn pt 1 m qt 2 n k in mathbb Z nbsp 其中t 1 t 2 displaystyle t 1 t 2 nbsp 為固定的整數 故二元組 p q displaystyle p q nbsp 要滿足0 lt p m 0 lt q n p m 1 q n 1 displaystyle 0 lt p leq m 0 lt q leq n p m 1 q n 1 nbsp 與小於m n displaystyle mn nbsp 且與m n displaystyle mn nbsp 互質的正整數N displaystyle N nbsp 一一對應 由f displaystyle varphi nbsp 的定義 和乘法原理 前一種數對 p q displaystyle p q nbsp 的個數為f m f n displaystyle varphi m varphi n nbsp 而後一種數N displaystyle N nbsp 的個數為f m n displaystyle varphi mn nbsp 所以 f m n f m f n displaystyle varphi mn varphi m varphi n nbsp 公式的證明 编辑 結合以上兩小節的結果可得 若n displaystyle n nbsp 有質因數分解式n p 1 k 1 p 2 k 2 p r k r displaystyle n p 1 k 1 p 2 k 2 cdots p r k r nbsp 則f n f i 1 r p i k i i 1 r f p i k i 积 性 i 1 r p i k i 1 p i 1 质 数 幂 处 取 值 n i 1 r 1 1 p i displaystyle quad begin aligned varphi n amp varphi left prod i 1 r p i k i right amp prod i 1 r varphi left p i k i right amp text 积 性 amp prod i 1 r p i k i 1 p i 1 amp text 质 数 幂 处 取 值 amp n prod i 1 r left 1 frac 1 p i right end aligned nbsp 例子 编辑 計算72 2 3 3 2 displaystyle 72 2 3 times 3 2 nbsp 的歐拉函數值 f 72 f 2 3 3 2 2 3 1 2 1 3 2 1 3 1 2 2 1 3 2 24 displaystyle varphi 72 varphi 2 3 times 3 2 2 3 1 2 1 times 3 2 1 3 1 2 2 times 1 times 3 times 2 24 nbsp 性质 编辑n的欧拉函数f n displaystyle varphi n nbsp 也是循环群 Cn 的生成元的个数 也是n阶分圆多项式的次数 Cn 中每个元素都能生成 Cn 的一个子群 即必然是某个子群的生成元 而且按照定义 不同的子群不可能有相同的生成元 此外 Cn 的所有子群都具有 Cd 的形式 其中d整除n 记作d n 因此只要考察n的所有因数d 将 Cd 的生成元个数相加 就将得到 Cn 的元素总个数 n 也就是说 d n f d n displaystyle sum d mid n varphi d n nbsp 其中的d为n的正约数 运用默比乌斯反转公式来 翻转 这个和 就可以得到另一个关于f n displaystyle varphi n nbsp 的公式 f n d n d m n d displaystyle varphi n sum d mid n d cdot mu n d nbsp 其中 m 是所谓的默比乌斯函数 定义在正整数上 對任何兩個互質的正整數a m 即 gcd a m 1 m 2 displaystyle m geq 2 nbsp 有 a f m 1 mod m displaystyle a varphi m equiv 1 pmod m nbsp 即欧拉定理 这个定理可以由群论中的拉格朗日定理得出 因为任意与m互质的a都属于环 Z n Z displaystyle mathbb Z n mathbb Z nbsp 的单位元组成的乘法群Z n Z displaystyle mathbb Z n mathbb Z times nbsp 當m是質數p時 此式則為 a p 1 1 mod p displaystyle a p 1 equiv 1 pmod p nbsp 即費馬小定理 生成函数 编辑以下两个由欧拉函数生成的级数都是来自于上节所给出的性质 d n f d n displaystyle sum d n varphi d n nbsp 由f displaystyle varphi nbsp n 生成的狄利克雷级数是 n 1 f n n s z s 1 z s displaystyle sum n 1 infty frac varphi n n s frac zeta s 1 zeta s nbsp 其中z s 是黎曼z函数 推导过程如下 z s f 1 f f f s g 1 1 g s f 1 f f f s displaystyle zeta s sum f 1 infty frac varphi f f s left sum g 1 infty frac 1 g s right left sum f 1 infty frac varphi f f s right nbsp h 1 f g h 1 f g 1 h s displaystyle sum h 1 infty left sum fg h 1 cdot varphi g right frac 1 h s nbsp h 1 f g h f g 1 h s h 1 d h f d 1 h s displaystyle sum h 1 infty left sum fg h varphi g right frac 1 h s sum h 1 infty left sum d h varphi d right frac 1 h s nbsp 使用开始时的等式 就得到 h 1 d h f d 1 h s h 1 h h s displaystyle sum h 1 infty left sum d h varphi d right frac 1 h s sum h 1 infty frac h h s nbsp 于是 h 1 h h s z s 1 displaystyle sum h 1 infty frac h h s zeta s 1 nbsp 欧拉函数生成的朗贝级数如下 n 1 f n q n 1 q n q 1 q 2 displaystyle sum n 1 infty frac varphi n q n 1 q n frac q 1 q 2 nbsp 其对于满足 q lt 1 的q收敛 推导如下 n 1 f n q n 1 q n n 1 f n r 1 q r n displaystyle sum n 1 infty frac varphi n q n 1 q n sum n 1 infty varphi n sum r geq 1 q rn nbsp 后者等价于 k 1 q k n k f n k 1 k q k q 1 q 2 displaystyle sum k geq 1 q k sum n k varphi n sum k geq 1 kq k frac q 1 q 2 nbsp 欧拉函数的走势 编辑随着n变大 估计f n displaystyle varphi n nbsp 的值是一件很难的事 当n为质数时 f n n 1 displaystyle varphi n n 1 nbsp 但有时f n displaystyle varphi n nbsp 又与n差得很远 在n足够大时 有估计 对每个 e gt 0 都有n gt N e 使得 n 1 e lt f n lt n displaystyle n 1 varepsilon lt varphi n lt n nbsp 如果考虑比值 f n n displaystyle varphi n n nbsp 由以上已经提到的公式 可以得到其值等于类似1 p 1 displaystyle 1 p 1 nbsp 的项的乘积 因此 使比值小的n将是两两不同的质数的乘积 由素数定理可以知道 常数 e 可以被替换为 C log log n log n displaystyle C log log n log n nbsp f displaystyle varphi nbsp 就平均值的意义上来说是与n很相近的 因为 1 n 2 k 1 n f k 3 p 2 O log n n displaystyle frac 1 n 2 sum k 1 n varphi k frac 3 pi 2 mathcal O left frac log n n right nbsp 其中的O表示大O符号 这个等式也可以说明在集合 1 2 n 中随机选取两个数 则当n趋于无穷大时 它们互质的概率趋于 6 p 2 displaystyle 6 pi 2 nbsp 一个相关的结果是比值f n n displaystyle varphi n n nbsp 的平均值 1 n k 1 n f k k 6 p 2 O log n n displaystyle frac 1 n sum k 1 n frac varphi k k frac 6 pi 2 mathcal O left frac log n n right nbsp 其他与欧拉函数有关的等式 编辑f n m n m 1 f n displaystyle varphi left n m right n m 1 varphi n nbsp a N n N l N displaystyle forall a in N forall n in N exists l in N nbsp 使得 a gt 1 n gt 1 l f a n 1 l n displaystyle a gt 1 land n gt 1 rightarrow l varphi a n 1 land l geq n nbsp a N n N l N displaystyle forall a in N forall n in N exists l in N nbsp 使得 a gt 1 n gt 6 4 n l f a n 1 l 2 n displaystyle a gt 1 land n gt 6 land 4 nmid n rightarrow l varphi a n 1 land l geq 2n nbsp d n m 2 d f d n f n displaystyle sum d mid n frac mu 2 d varphi d frac n varphi n nbsp 1 k n k n 1 k 1 2 n f n for n gt 1 displaystyle sum 1 leq k leq n atop k n 1 k frac 1 2 n varphi n text for n gt 1 nbsp k 1 n f k 1 2 1 k 1 n m k n k 2 displaystyle sum k 1 n varphi k frac 1 2 left 1 sum k 1 n mu k left lfloor frac n k right rfloor 2 right nbsp k 1 n f k k k 1 n m k k n k displaystyle sum k 1 n frac varphi k k sum k 1 n frac mu k k left lfloor frac n k right rfloor nbsp k 1 n k f k O n displaystyle sum k 1 n frac k varphi k mathcal O n nbsp k 1 n 1 f k O log n displaystyle sum k 1 n frac 1 varphi k mathcal O log n nbsp 与欧拉函数有关的不等式 编辑f n gt n e g log log n 3 log log n displaystyle varphi n gt frac n e gamma log log n frac 3 log log n nbsp 其中n gt 2 g 为欧拉 马歇罗尼常数 f n n 2 displaystyle varphi n geq sqrt frac n 2 nbsp 其中n gt 0 对整数n gt 6 f n n displaystyle varphi n geq sqrt n nbsp 当n为质数时 显然有f n n 1 displaystyle varphi n n 1 nbsp 对于合数的n 则有 f n n n displaystyle varphi n leq n sqrt n nbsp 程式代码 编辑C 编辑 template lt typename T gt inline T phi T n T ans n for T i 2 i i lt n i if n i 0 ans ans i i 1 while n i 0 n i if n gt 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页 Kevin Ford The number of solutions of f x m Ann of Math 150 1999 283 311 页面存档备份 存于互联网档案馆 柯召 孙琦 数论讲义 上册 第二版 高等教育出版社 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 取自 https zh wikipedia org w index php title 欧拉函数 amp oldid 79918283, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。