數論(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 原語餓狼 閱讀(801) 評論(0)  編輯 收藏 引用 所屬分類: 數論