尤拉函數 Euler φ function(筆記)

最近看書一直碰到尤拉函數，寫個筆記複習一下。

定義：尤拉φ函數

若n為自然數，定義φ(n)為不大於n且與n互質的自然數的個數。

Note: φ(1)＝1

尤拉φ函數的算法：

若，其中p₁, p₂, …, p_r均為質數，則φ(n)即為所有不比n大且不是p₁, p₂, …, p_r這些質數的倍數的數之個數，即

也可以用另一個觀點來說明尤拉φ函數的算法：

首先要先說明，若a和b互質，則φ(ab)＝φ(a)×φ(b)：

若a＝b＝1，顯然成立。

若ab≠1，不失一般性，假設a＞b，因為不大於a的自然數中，有φ(a)個數與a互質，設為a₁, a₂, …,a_φ(a)，則對於1≦i≦φ(a)，{ a_i, a_i＋a, a_i＋2a, …, a_i＋(b－1)a}是一個模b的完全剩餘系(complete residue system)^註，所以有φ(b)個數與b互質，當然也與ab互質，故總共有φ(a)×φ(b)個數與ab互質。

^註：模n的完全剩餘系指的是有n個元素的集合，其中每一個元素在模n時都互不同餘，也就是說這n個元素模n後與{0, 1, 2, …, n－1}相同。

舉例來說，我們考慮不大於72且與72互質的數，因為72＝9×8，則可以列出如下的9行8列的陣列，再將與9不互質的數刪掉，則就只剩下φ(9)＝6行。剩下的每一行有8個數，恰是模8的完全剩餘系，只有φ(8)＝4個數與8互質(即框起來的數)，這些數即所有不大於72且與72互質的數，共有φ(9)×φ(8)＝24個。即φ(72)＝24。

1	2	3	4	5	6	7	8	9
10	11	12	13	14	15	16	17	18
19	20	21	22	23	24	25	26	27
28	29	30	31	32	33	34	35	36
37	38	39	40	41	42	43	44	45
46	47	48	49	50	51	52	53	54
55	56	57	58	59	60	61	62	63
64	65	66	67	68	69	70	71	72

實際上，只要一個算術函數(arithmetic function，定義域為正整數的函數) f，滿足f(ab)＝f(a)f(b)，其中a和b互質，就稱函數f為積性函數(multiplicative function)，因此對於任意的自然數n，將n作質因數分解成，則。上面的敘述即在說明φ是一個積性函數，故。而任意質數p的冪次p^k都只有p這一個質因數，因此不大於p^k且與p^k不互質的數只有p、2p、…、p^k共p ^k­-1個數，故φ(p^k)＝p^k－p^k-1＝p^k(1－1/p)。所以可以得到φ(n)＝n(1－1/p₁) (1－1/p₂)…(1－1/p_r)，其中p₁、p₂、…、p_r是n所有的質因數。