yuanyuelang

数论(3)-------欧拉phi函数

欧拉phi函数


1.应用：
  对一个正整数n,求小于n且与n互质（包括1）的个数。

2.公式：
  

         I
Φ(n) =n ∏ (1 - 1 / pi)，其中pi表示n的质因子，
        i=1

    I
n = ∏ (Pi)^ki  (I 为 n 的素因子的个数)
   i=1

如：Φ（10）=10（1-1/2)(1-1/5)=4,其中2,5是10的质因子.

3.证明：
   
   要证明这个式子，我们先来看几个基本的公式。
   
   （1）  Φ(p)=p-1,p是质数
   （2）  Φ(p*q)=Φ(p)Φ(q)  p,q是质数

         Φ(p*q)=p*q-1- (q-1)(注：【p,2p,...(q-1))】个数q-1） -(p-1)(注：【q,2q,...(p-1)q】个数p-1)
              =(p-1)(q-1)=Φ(p)Φ(q)

    (3)  对于整数n,n=p^k
               φ(n) = p^k - p^k-1 
         小于 pk 的正整数个数为 pk - 1个，其中
         和 pk 不互质的正整数有{p * 1,p * 2,...,p * (p^k-1-1)} 共计 p^k-1- 1 个
         所以 φ(n) = p^k -1 ( p^k-1- 1) = p^k-p^k-1 。
       

     接下来要证明上面那个欧拉函数就是轻而易举的事情了。

 1int phi(int n)
 2{
 3    int ans,i,k;
 4    if(n==1) 
 5        ans=0;
 6
 7    else{        
 8      ans=n;
 9      k=1;
10      for(i=2;n!=1;i+=k){
11        if(n%i==0){
12            ans*=(i-1);ans/=i;
13            while(n%i==0) n/=i;
14            i=k;
15        }
16
17      }
18    }
19    return ans;
20}

posted on 2009-09-05 18:51 原语饿狼 阅读(779) 评论(0)  编辑 收藏 引用 所属分类: 数论