歐拉函數_歐拉定理_擴充歐拉定理

歐拉函數

• 定義：對于正整數n，歐拉函數是小于n的正整數中與n互質的數的數目
• 通式：

  

  【其中：p1,p2,...,pn為x的所有質因數，x是不為0的整數】
• 特别說明：φ(1)=1：和1互質的數（<=1）就是1本身
• 性質：

1. 若n為質數，φ(n)=n-1
2. 若m,n互質，φ(mn)=φ(m)φ(n)
3. 當n為奇質數時，φ(2n)=φ(n)
4. 當n=p^k，且p是質數時，

   

                 證明：[1,n-1]即[1,p^k-1]區間有整數p^k-1個

                            與p^k不互質的數有{p,2p,3p,4p,...,p^k-p(=(p^(k-1)-1)*p}明顯有p^(k-1)-1個

                            于是前者-後者得到：

                                                也就是：

//歐拉函數模闆

bool Is_Prime(ll x)
{
    if( x == 2 ) return true;
    for(ll i = 2 ; i * i <= x ; i++)
    {
        if( x % i == 0)
            return false;
    }
    return true;
}

set<ll> st;

void prime_factor(ll x)
{
    for(ll i = 2 ; i <= x ; i++)
    {
        if(Is_Prime(x))
        {
            st.insert(x) ;
            return ;
        }
        if(Is_Prime(i))
        {
            while(x % i == 0)
            {
                x /= i;
                st.insert(i);
            }
        }
    }
}

ll Euler(ll x)
{
    if(x == 1) return 1;
    ll up = x, down = 1;
    prime_factor(x);
    while(! st.empty())
    {
        int tmp = *st.begin();
        st.erase(st.begin());
        up *= (tmp - 1);
        down *= tmp;
    }
    return up / down;
}
           

歐拉定理

同餘定理：

• 兩個整數a,b，若它們除以整數m所得的餘數相等，則稱a與b對模m同餘或a同餘于b模m，記作：a≡b(mod m)
• 給定一個整數m，如果兩個整數a,b滿足(a-b)%b=0，那麼a與b對模m同餘，記作a-b≡0(mod m)，也即m|(a-b)

内容：

• 

    其中a和m互質

     證明：

       假設小于m且與m互質的數為{x[1],x[2],x[3],...,x[φ(m)]}，令p[ i ]=a*x[ i ]，得到{p[1]=a*x[1], p[2]=a*x[2], ... ,p[φ(m)]=a*x[φ(m)]}

引理1：

• p[ ]之間兩兩對于模m不同餘；x[ ]之間兩兩對于模m不同餘 

    證明：

    假設p[ i ]和p[ j ]對于模m同餘(p[ i ]>p[ j ]，i != j)，即p[ i ]-p[ j ] Ξ 0 (mod m)

    那麼m|p[ i ]-p[ j ]  ->  m|a(x[ i ]-x[ j ])

    設a(x[ i ]-x[ j ])=km  (k是整數)

    因為a和m互質，是以由上式的恒等性可以得到：x[ i ]-x[ j ]和m不互質，且x[ i ]-x[ j ]是m的倍數，即x[ i ]-x[ j ] Ξ 0 (mod m)，也就是x[ i ]與x[ j ]對模m同餘

     又因為x[ i ]和x[ j ]都與m互質，且都小于m，是以與上述結論沖突

     得證。

引理2：

• 每個p[ ]模m的結果都與m互質

    證明：

    假設p[ i ]=ax[ i ]=km+r, gcd(r,m)>1【也就是r和m有公因子，我們設為d，也即d|r，d|m】

    原式可以化為：ax[ i ]=d*(km/d+r/d)，即 d|ax[ i ]

    因為a和m互質，x[ i ]和m互質，是以ax[ i ]和m互質，與上述結論沖突

    得證

由上面兩個引理我們可以得到：

       p[ ]%m的集合和x[ ]的集合相等，即p[ ]重新排序後與x[ ]對應，兩兩對模m同餘。

       我們将p[ ]相乘 ：

 = 

* 

       因為p[ i ] Ξ x[ i ] (mod m)

       是以

 Ξ 

 (mod m)  【由引理1和歐拉函數的性質2】

       也即

 * 

 Ξ 

 (mod m)

       即

 Ξ 1 (mod m)

      至此，歐拉定理得證

費馬小定理

• p為質數，整數a不是p的倍數，則a^(p-1)Ξ1(mod p)

擴充歐拉定理

•