( 1 ) p^k 的歐拉函數

對于給定的一個素數 p ， φ(p) = p -1。則對于正整數 n = p^k ，

 φ(n) = pk - pk -1
  
證明：
 小于 pk 的正整數個數為 pk - 1個，其中
 和 pk 不互質的正整數有{p * 1,p * 2,...,p * (pk - 1-1)} 共計 pk - 1 - 1 個
 所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。

( 2 ) p * q 的歐拉函數

假設 p, q是兩個互質的正整數，則 p * q 的歐拉函數為

φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。

證明：
 令 n = p * q ， gcd(p,q) = 1
 根據中國余數定理，有
 Zn 和 Zp × Zq 之間存在一一映射
（我的想法是： a ∈ Zp ， b ∈ Zq ⇔ b * p + a * q ∈ Zn 。）
 所以 n 的完全余數集合的元素個數等于集合 Zp × Zq 的元素個數。
 而后者的元素個數為 φ(p) * φ(q) ，所以有
 φ(p * q) = φ(p) * φ(q) 。

( 3 ) 任意正整數的歐拉函數

任意一個整數 n 都可以表示為其素因子的乘積為：

        I
 n = ∏  piki (I 為 n 的素因子的個數)
     i=1

根據前面兩個結論，很容易得出它的歐拉函數為：

           I                        I
 Φ(n) = ∏  piki -1(pi -1) = n ∏ (1 - 1 / pi)
          i=1                    i=1

對于任意 n > 2，2 | Φ(n) ,因為必存在  p_i -1 是偶數。

程序代碼可參見：http://blog.csdn.net/Rappy/archive/2007/08/16/1747489.aspx