欧拉函数公式

欧拉函数公式

p^k的欧拉函数

对于给定的一个素数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)