关于欧拉定理的证明以及扩展欧拉定理的证明及其应用

• 前置芝士：

　　欧拉函数（φ(p)）:即指在[1,p-1][1,p−1]中与p互质的数的个数，特别的，φ(1)=1。

• 单数值求欧拉函数：（时间复杂度O（√n））

• int euler(int n){ //返回euler(n)   
     int res=n,a=n;  
     for(int i=2;i*i<=a;i++)  
         if(a%i==0){  
              res=res/i*(i-1);  
              while(a%i==0) a/=i;  
          }  
      }  
      if(a>1) res=res/a*(a-1);  
      return res;  
  }

• 线性筛欧拉函数：（时间复杂度O（n））

• void getphi(){  
      phi[1]=1;  
      for(i=2;i<=N;i++){//相当于分解质因式的逆过程 
          if(!mark[i]){  
              prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。  
              phi[i]=i-1;//当 i 是素数时 phi[i]=i-1  
          }  
          for(j=1;j<=tot;j++){  
              if(i*prime[j]>N)  break;  
              mark[i*prime[j]]=1;//确定i*prime[j]不是素数  
                if(i%prime[j]==0){//接着我们会看prime[j]是否是i的约数   
                   phi[i*prime[j]]=phi[i]*prime[j];
                   break;
              }
                else  phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性  
         }  
     }  
  }

• Eg：通式：

  

  欧拉定理

• 

  引入概念

  基本概念——完全剩余系：从模n的每个剩余类中各取一个数，得到一个由0到n-1，n个数组成的集合，叫做模n的一个完全剩余系。

  就是说刚好取遍所有mod p意义下余数的任意一个数的集合。

 

　　

引入引理

 

 

---

 

---

下面是对于欧拉定理的证明

 

左右同时约分可得：

 

 

---

  扩展欧拉定理及其证明

 

 证明： 附链接[(https://blog.csdn.net/can919/article/details/82318115)]

 

 对于质数的幂在mod（m）的意义下：

又

 

 

 所以

 

 综述：

得证。

---

 

• 下面是 扩展欧拉定理（P5091）模板代码（读入时根据扩展欧拉定理优化取模）

• #pragma GCC optimize(2)
  #include<cstring>
  #include<cstdio>
  #include<cmath>
  #include<iostream>
  #include<cctype>
  #include<ctime>
  #include<cstdlib>
  #include<map>
  #include<algorithm>
  
  using namespace std;
  
  #define ll long long 
  
  ll a,m,b;
  
  ll power(ll a,ll b,ll m);
  inline ll read();
  inline ll read_(ll m);
  inline void write(ll x);
  ll euler(ll n);
  
  int main(){
      a=read();m=read();
      b=read_(euler(m));
      write(power(a,b,m));
  }
  
  ll power(ll a,ll b,ll m){
      ll ret=1;
      while(b){
          if(b&1) ret=ret*a%m;
          a=a*a%m;
          b>>=1;
      }
      return ret;
  }
  
  inline ll read(){
      ll a=1,b=0;char t;
      while(t<'0'||t>'9'){
          if(t=='-') a=-1;
          t=getchar();
      }
      while(t>='0'&&t<='9') b=b*10-'0'+t,t=getchar();
      return a*b;
  }
  
  inline ll read_(ll m){
      bool flag=0;
      ll y=0;char t=getchar();
      while(t<'0'||t>'9') t=getchar();
      while(t>='0'&&t<='9'){
          y=y*10-'0'+t;
          if(y>=m) flag=1;
          y%=m;
          t=getchar();
      }
      if(flag) return y+m;
      return y;
  }
  
  inline void write(ll x){
      ll fig[33],top=0;
      if(!x) putchar('0');
      while(x) fig[++top]=x%10,x/=10;
      while(top) putchar(fig[top--]+'0');
  }
  
  ll euler(ll n){
      ll res=n,a=n;
      for(int i=2;i*i<=a;i++)
          if(!(a%i)){
          res=res/i*(i-1);
          while(!(a%i)) a/=i;
      }
      if(a>1) res=res/a*(a-1);
      return res;
  }