尤拉φ函數(筆記)

前幾天在上競賽的培訓課時，講到尤拉函數(Euler’s φ function)，一位協助指導的老師提供了一個用機率的「獨立事件」的觀點的說明方法，記錄如下：

定義(尤拉φ函數)：

設n為自然數，φ(n)定義為小於n且與n互質的正整數的個數。

首先看一道題目：α、β、γ為正整數，試求小於n=2^α×3^β×5^γ，且不是2，不是3，也不是5的倍數有幾個(即求φ(n)的值)？
設一個試驗為從1~30的整數中，任選一數，則樣本空間S={1, 2, ..., 30}，A為2的倍數的事件，B為3的倍數的事件，C為5的倍數的事件。

顯然A∩B為2×3=6的倍數的事件，B∩C為3×5=15的倍數的事件，C∩A為5×2=10的倍數的事件，A∩B∩C為2×3×5=30的倍數的事件。

故P(A)=1/2，P(B)=1/3，P(C)=1/5，P(A∩B)=P(A)×P(B)=1/6，P(B∩C)=P(B)×P(C)=1/15，P(C∩A)=P(C)×P(A)=1/10，P(A∩B∩C)=P(A)×P(B)×P(C)=1/30。

所以A、B、C為獨立事件。所以若從小於n的數中選出不是2、3、5的倍數的數的事件為A’∩B’∩C’，機率為P(A’∩B’∩C’)=(1- P(A))(1－P(B))(1－P(C))=(1－1/2)(1－1/3)(1－1/5)，故φ(n)=n×(1－1/2)(1－1/3)(1－1/5)

實際上，上面的題目講的是：

設p₁、p₂、…、p_r是n所有相異的質因數。若從1~n的整數中任取一數，A₁、A₂、…、A_r分別是取到p₁、p₂、…、p_r的倍數的事件，則A₁’ ∩A₂’ ∩…∩A_r’即為取到的整數為與n互質的數的事件。

因為p₁、p₂、…、p_r兩兩互質且都是n的因數，所以A₁、A₂、…、A_r是獨立事件，當然A₁’、A₂’、…、A_r’ 也是獨立事件，故

P(A₁’ ∩A₂’ ∩…∩A_r’)= P(A₁’)P(A₂’)…P(A_r’)=(1－1/p₁) (1－1/p₂)…(1－1/p_r)，

φ(n)＝nP(A₁’ ∩A₂’ ∩…∩A_r’)=n(1－1/p₁) (1－1/p₂)…(1－1/p_r)。

尤拉函數 Euler φ function(筆記)