( 1 ) pk 的欧拉函数
对于给定的一个素数 p ， φ(p) = p -1。则对于正整数 n = pk ，
φ(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) ,因为必存在 pi -1 是偶数。