Skip to content

欧拉函数

欧拉函数的定义

就是对于一个正整数\(n\)，小于\(n\)且和\(n\)互质的正整数（包括\(1\)）的个数，记作\(\phi(n)\) 。

\[\phi(x)=x\prod_{i=1}^n(1-\frac{1}{p_i})\]

线性筛求欧拉函数

1.性质法(欧拉筛) O(n)

  1. \(\phi(i* j)_ {j|i}=\phi(i)* j\)
  2. \(\phi(i* j)_ {j⊥i}=\phi(i)* \phi(j)\) 
        euler[1]=0;
    for(int i=1;i<=n;++i)v[i]=1;
    for(int i=2;i<=n;++i){
        if(v[i]==1){
            p[++m]=i;
            euler[i]=i-1;
        }
        for(int j=1;j<=m;++j){
            if(p[j]*i>n)break;
            v[p[j]*i]=0;
            if(i%p[j]==0){
                euler[i*p[j]]=euler[i]*p[j];break;
            }else{
                euler[i*p[j]]=euler[i]*euler[p[j]];
            }
        }
    }

2.定义法 O(nlogn)

    phi[i]=1;
    for(int i=2;i<=n;++i){
        if(!phi[i]){//i是个质数，则要枚举它的倍数，更新这些倍数j
            for(int j=i;j<=n;j+=i){
                if(!phi[j])phi[j]=j;//初始化为j
                phi[j]=phi[j]/i*(i-1);//i是j的一个质因子
            }
        }
    }

欧拉函数的性质：

  1. 若\(p\)为质数，则\(\phi(p)=p-1\)

  2. 若\(n=p^k\)且\(p\)为质数，则\(\phi(n)=p^k-p^{k-1}\)

  3. 若\(m⊥n\)，有\(\phi(m* n)= \phi(m)* \phi(n)\); 若\(m|n\)，有\(\phi(m* n) = m * \phi(n)\)

  4. 欧拉定理，若\(m⊥a\),则\(a^{\phi(m)}\equiv 1\pmod m\)

  5. 当\(n\)为奇数时，\(\phi(2n)=\phi(n)\)

  6. \(n=\sum_{d|n}\phi(d)\)

给出其中一些定理的证明：

性质1

因为\(p\)为质数，所以所有小于他的\(p-1\)个数都与它互素。

性质2

\(n\)只有一个质因数\(p\),所以根据定义\(\phi(n)=n(1-\frac1p)=p^k-p^{k-1}\)

性质3

1.

因为\(m⊥n\),所以\(m\)与\(n\)无公共质因数

所以设\(m\)由\(a_m\)个质因数，\(n\)由\(a_n\)个质因数。

\[\therefore \phi(m)* \phi(n)=m * n * \prod_{i=1}^{a_m}(1-\frac{1}{p_i}) * \prod_{i=1}^{a_n}(1-\frac{1}{p_i})\\ =(m* n) * \prod_{i=1}^{a_m+a_n}(1-\frac{1}{p_i}) =\phi(m* n) \]

2.

因为\(m|n\),所以\(n\)包含了\(m\)的所有质因数。

所以设\(n\)含有的相同的质因数为\(a_n\),则\(m * n\)所含质因数与\(n\)完全相同.(不计质因子个数)

\[\therefore \phi(m * n)=m * n * \prod_{i=1}^{a_n}(1-\frac{1}{p_i}) \\ =m*\phi(n)\]

性质6

  1. 证\(F(n)=\sum_{d|n}\phi(d)\)为积性函数

设 \(F(m)* F(n)=\sum_{i|m}\phi(i) * \sum_{j|n}\phi(j)=\phi(i_1)* \phi(j_1)+\phi(i_1)* \phi(j_2)+...+\phi(i_{k_m})* \phi(j_{k_n})\)

因为\(m⊥n\)，所以所有的\(i\)与\(j\)互质，所以原式\(=\phi(i_1* j_1)+...+\phi(i_{k_m}* \phi(j_{k_n}))\)

又因为\(i_1* j_1,...,i_{k_m}* j_{k_n}\)构成了\(m* n\)所有因数，所以\(F(m) * F(n)=F(m* n)\).

2.证明\(F(p^k)=\sum_{d|p^k}\phi(d)\)

因为\(p^k\)的因数只有\(1,p,p^2,...,p^k\).

所以\(F(p^k)=\phi(1)+\phi(p)+...+\phi(p^k)=1+p-1+p^2-p+...+p^k-p^{k-1}=p^k\)

  1. 推广

因为对于任意\(p\)为质数，\(F(p^k)\)符合条件，而\(F\)为积性函数，所以可以推广到任意正整数。