pk的欧拉函数
对于给定的一个素数p，我们知道Φ(p) = p-1。假设一个整数n是p的k次幂，也就是
n = pk k∈N+
容易证明
Φ(n) = pk - pk-1
证明：
已知少于小于pk的正整数个数为pk-1个，其中
和pk不互质的正整数有{p×1,p×p2,...,p×(pk-1-1)}共计pk-1-1个
所以Φ(n) = pk -1 - (pk-1-1) = pk - pk-1
pq的欧拉函数
假设p,q是两个互质的正整数，则pq的欧拉函数为
Φ(pq) = Φ(p)Φ(q) gcd(p,q)=1
证明：
∵M= pq,gcd(p,q) =1
∴根据中国余数定理，有
ZM和Zp×Zq之间存在一一映射
所以M的完全余数集中元素的个数等于集合Zp×Zq元素的个数
而后者的元素个数为Φ(p)Φ(q)，所以有
Φ(pq) = Φ(p)Φ(q)
任意正整数的欧拉函数
任意一个整数n都可以表示为其素因子的乘积为：
I
n = ∏ piki
i=1
根据前面两个结论，很容易得出它的欧拉函数为：
I
Φ(n) = ∏ piki-1(pi-1)
i=1
对于任意n>2，很显然，2 | Φ(n)