歐拉函數是什么

在數論，對正整數 n，歐拉函數是小于或等于 n 的正整數中與 n 互質的數的數目（因此φ(1)=1）。此函數以其首名研究者歐拉命名(Euler’s totient function)，它又稱為 Euler’s totient function、φ函數、歐拉商數等。 例如φ(8)=4，因為 1,3,5,7 均和 8 互質。 從歐拉函數引伸出來在環論方面的事實和拉格朗日定理構成了歐拉定理的證明。

函數內容

通式：

(其中 p1, p2……pn 為 x 的所有質因數，x 是不為 0 的整數)

定義 φ(1)=1（和 1 互質的數(小于等于 1)就是 1 本身）。

注意：每種質因數只有一個。

比如 12=2*2*3 那么φ（12）=φ（4*3）=φ（2^2*3^1）=（2^2-2^1）*（3^1-3^0）=4

若 n 是質數 p 的 k 次冪，

，因為除了 p 的倍數外，其他數都跟 n 互質。

設 n 為正整數，以 φ(n)表示不超過 n 且與 n 互素的正整數的個數，稱為 n 的歐拉函數值

φ：N→N，n→φ(n)稱為歐拉函數。

歐拉函數是積性函數——若 m,n 互質，

特殊性質：當 n 為奇質數時，

, 證明與上述類似。

若 n 為質數則

證明

設 A, B, C 是跟 m, n, mn 互質的數的集，據中國剩余定理，A*B 和 C 可建立一一對應的關系。因此φ(n)的值使用算術基本定理便知，

若

則

例如

與歐拉定理、費馬小定理的關系

對任何兩個互質的正整數 a, m(m>=2)有

即歐拉定理

當 m 是質數 p 時，此式則為：

即費馬小定理。

編程實現

利用歐拉函數和它本身不同質因數的關系，用篩法計算出某個范圍內所有數的歐拉函數值。

歐拉函數和它本身不同質因數的關系：

歐拉函數ψ（N）=N{∏p|N}（1－1/p）

亦即:

（P 是數 N 的質因數）

如：

ψ（10）=10×（1－1/2）×（1－1/5）=4；

ψ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8；

ψ（49）=49×（1－1/7）=

=42。