歐拉函數(shù)是什么

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

函數(shù)內(nèi)容

通式：

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

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

注意：每種質(zhì)因數(shù)只有一個(gè)。

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

若 n 是質(zhì)數(shù) p 的 k 次冪，

，因?yàn)槌?p 的倍數(shù)外，其他數(shù)都跟 n 互質(zhì)。

設(shè) n 為正整數(shù)，以 φ(n)表示不超過(guò) n 且與 n 互素的正整數(shù)的個(gè)數(shù)，稱(chēng)為 n 的歐拉函數(shù)值

φ：N→N，n→φ(n)稱(chēng)為歐拉函數(shù)。

歐拉函數(shù)是積性函數(shù)——若 m,n 互質(zhì)，

特殊性質(zhì)：當(dāng) n 為奇質(zhì)數(shù)時(shí)，

, 證明與上述類(lèi)似。

若 n 為質(zhì)數(shù)則

證明

設(shè) A, B, C 是跟 m, n, mn 互質(zhì)的數(shù)的集，據(jù)中國(guó)剩余定理，A*B 和 C 可建立一一對(duì)應(yīng)的關(guān)系。因此φ(n)的值使用算術(shù)基本定理便知，

若

則

例如

與歐拉定理、費(fèi)馬小定理的關(guān)系

對(duì)任何兩個(gè)互質(zhì)的正整數(shù) a, m(m>=2)有

即歐拉定理

當(dāng) m 是質(zhì)數(shù) p 時(shí)，此式則為：

即費(fèi)馬小定理。

編程實(shí)現(xiàn)

利用歐拉函數(shù)和它本身不同質(zhì)因數(shù)的關(guān)系，用篩法計(jì)算出某個(gè)范圍內(nèi)所有數(shù)的歐拉函數(shù)值。

歐拉函數(shù)和它本身不同質(zhì)因數(shù)的關(guān)系：

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

亦即:

（P 是數(shù) N 的質(zhì)因數(shù)）

如：

ψ（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。