欧拉定理&欧拉函数

定义

欧拉函数$\phi$(Euler’s totient function),$\phi(n)$定义为$[1,n]$中与$n$互质的数的个数。
欧拉定理: $a^{2\phi(n)}\equiv a^{\phi(n)}\pmod n$

性质

1. $a^{\phi(p)} \equiv 1\pmod p$
   要求$a$与$p$互质;

2. 设$\phi(x)=\prod_{p_i}^{k_i}$,那么
   $\phi(x)=\prod (1-\frac{1}{p_i})=\prod(p_i-1)_{p_i}^{k_1-1}$;

3. $\phi(\mathsf{质数}x)=x-1$;
   $\phi(\mathsf{互质}x \times y)=\phi(x)\times \phi(y)$;
   $\phi(\mathsf{质数 }x\mathsf{ 是y的因子} \times y)=x \times \phi(y)$;

4. 欧拉函数是积性函数:
   若$(a,b)=1$,则$\phi(ab)=\phi(a)\phi(b)$

5. 设$p$为$n$的一个质因子，$k$为$p$的次数，则有$\phi(n) \geq k$成立

   • 证明：设$n=p^k \times t$，那么 $\phi(n)=\phi(p^k)\phi(t) \geq \phi(p^k) \geq k$

计算

1. 一种基于质因数分解求欧拉函数的算法(求单个$\phi$)

   int phi(int x){
       int ret = x;
       int t=sqrt(x);
       for(int i =2;i<=t;i++){
           if(x%i==0){
               while(x%i==0)x/=i;
               ret = ret / i * (i - 1);
           }
       }
       if(x>1) ret=ret/x*(x-1);
       return ret;
   }

2. 线性筛欧拉函数

   const int N = 1e6 + 10;
   int n, cnt;//cnt标记素数个数
   int phi[N];//存每个数的欧拉函数
   int prim[N];//存放素数
   bool vis[N];//判断是不是素数
   int ans;
   
   int getphi(int n){
       phi[1] = 1;
       for(int i = 2; i <= n; i++){
           if( !vis[i] ){
               prim[++cnt] = i;
               phi[i] = i - 1;
           }
           for(int j = 1; j <= cnt; j++){
               if(i * prim[j] > n) break;
               vis[i * prim[j]] = true;
               if(i % prim[j] == 0){
                   phi[i * prim[j]] = prim[j] * phi[i];break;
               }
               else{
                   phi[i * prim[j]] = phi[i] * (prim[j] - 1);
               }
           }
       }
       for(int i = 1; i <= n; i++){
           ans += phi[i];
       }
       return ans;
   }

应用

用欧拉定理求逆元：$a \times a^{\phi(n)-1} \equiv 1 \pmod n$;
特别的，若$n$为质数：$a \times a^{n-2} \equiv 1 \pmod n$
快速幂即可

int powermod(int a, int b, int n){
    int ret = 1;
    while(b){
        if(b & 1) ret=(long long)ret*a%n;
        a=(long long)a*a%n;
        b>>=1;
    }
    return ret;
}