（所有^为次方）
欧拉定理：
a^phi(m)=1 (mod m) ( gcd(a,m)=1 )
设1到m中与m互质的数为
x1, x2, x3, ……x phi(m)
令pi=xi*a
引理一：p之间两两模m不同余，x之间两两模m不同于
x两两模m不同样因为都小于等于m，一眼看出
反证：若pi-pj=0（mod m）（i≠j） ，则a（xi – xj）=0 （mod m）
gcd（a，m）=1，则 xi – xj = 0 （mod m），矛盾
所以p之间两两模m不同余
引理二：每个p模m的结果与m互质
反证：若a*xi = km + r ,gcd(r,m)>1
则 a*xi – km = r 根据扩展欧几里得，gcd（a，m）=1
则最后解出来的x要乘上r，与gcd（x，m）互质矛盾
所以每个p模m的结果与m互质
由这两个引理
∏pi = xi （mod m） -> ( a^phi(m) )*∏xi = ∏xi (mod m)
gcd( ∏xi, m ) = 1 -> a^phi(m) = 1 ( mod m )
扩展欧拉定理：
a^c = { a^( c%phi(m) ) , gcd( a,m) =1
a^c , gcd( a,m )≠1，c<phi(m)
a^( c%phi(m) + phi(m) ), gcd( a,m )≠1, c>=phi(m)
}
1. a^c=a^( c%phi(m) ) , gcd( a,m) =1
这个由欧拉定理可知，在mod m 意义下，
a^phi(m)=1, a^0 =1 -> a^x 以phi(m)为循环节
2. a^c=a^c , gcd( a,m )≠1，c<phi(m)
不用证
3. a^c=a^( c%phi(m) + phi(m) ), gcd( a,m )≠1, c>=phi(m)
首先证明对m的一个质数因子p
有p^c = p^( c%phi(m) +phi(m) ) (mod m) , c>phi(m)
令 m= s * p^r , gcd(s,p)=1
有p^phi(s) = 1 (mod s) ,又gcd(s,p) =1
则phi(m) = phi(s) * phi(p^r) -> phi(s) | phi(m)
则p^phi(m) =1 (mod s) -> p^phi(m) = k*s +1;
两边同乘p^r, p^( phi(m) +r ) = k*m + p^r
即p^( phi(m) + r ) = p^r (mod m ) -> p^r = p^( k*phi(m) +r ) ( mod m ) (k>=0)
显然有 phi(m) = phi(s)* phi(p^r) >= phi(p^r) = (p^(r-1) )*(p-1)>=p^(r-1) >= r
所以有 p^c = p ^( c-r + r) = p^(c-r + r+phi(m) ) =p^( c+phi(m) ) , c>=r
则 p^c = p^(c%phi(m) + phi(m) ) ( mod m ) , c>=phi(m)
则对于p的幂也一样有
(p^k)^c = p^(k*c) = p^(phi(m) +k*c ) = p^(k*phi(m) + k*c) = (p^k)^( c+phi(m) )
= ( p^k )^(c%phi(m) + phi(m) ) (mod m) , c>=phi(m), k>0
令a=∏pi^ki，则对于每一个pi^ki 都满足上述式子，则相乘后
有 a^c = a^( c%phi(m) + phi(m) ) (mod m), c>=phi(m)
证毕
基本上是看https://blog.csdn.net/hzj1054689699/article/details/80693756 这个blog的，加了中间的一些解释和过程