歐拉函數

以歐拉命名的數論函數

在數論，對正整數n，歐拉函數是小於n的正整數中與n互質的數的數目。

目錄

1函數內容 2證明 3編程實現

函數內容

通式：

其中為的所有質因數，是不為0的整數。

（和1互質的數(小於等於1)就是1本身）。

注意：每種質因數只一個。比如那麼若n是質數p的k次冪，，因為除了的倍數外，其他數都跟互質。

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

稱為歐拉函數。

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

特殊性質：當n為質數時， , 證明與上述類似。

若n為質數則

證明

設是跟互質的數的集，據中國剩餘定理，和可建立一一對應的關係。因此的值使用算術基本定理便知，

若

則

例如

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

對任何兩個互質的正整數有

即歐拉定理

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

即費馬小定理。

編程實現

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

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

歐拉函數

亦即: （P是數N的質因數）

如：

函數表

0~100歐拉函數表（“x?”代表十位數，“x”代表個位數）
φ(n)		1	2	3	4	5	6	7	8	9
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

目錄