歐拉函式

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

基本信息

• 中文名：歐拉函式
• 別稱：Euler's totient function、φ函式、歐拉商數
• 定義：在數論，對正整數n，歐拉函式varphi(n)是少於或等於n的數中與n互質的數的數目
• 計算公式：當m是質數p時，此式則為：a^ \equiv 1 \pmod p

函式內容

歐拉函式

通式：

其中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。

C++版

pascal版

C語言

Java語言

C#語言

函式表

0~100歐拉函式表（“x?”代表十位數，“x”代表個位數）

φ(n)	0	1	2	3	4	5	6	7	8	9
0?	0	1	1	2	2	4	2	6	4	6
1?	4	10	4	12	6	8	8	16	6	18
2?	8	12	10	22	8	20	12	18	12	28
3?	8	30	16	20	16	24	12	36	18	24
4?	16	40	12	42	20	24	22	46	16	42
5?	20	32	24	52	18	40	24	36	28	58
6?	16	60	30	36	32	48	20	66	32	44
7?	24	70	24	72	36	40	36	60	24	78
8?	32	54	40	82	24	64	42	56	40	88
9?	24	72	44	60	46	72	32	96	42	60

φ(100)=40