扩展欧拉定理

  • 扩展欧拉定理通常用于快速模幂中的降幂，其内容为：ab≡{ab mod φ(m),gcd⁡(a,m)=1a(b mod φ(m))+φ(m),gcd⁡(a,m)≠1,b≥φ(m)ab,gcd⁡(a,m)≠1,b<φ(m)    (mod m)a^b\equiv\begin{cases}a^{b\ {\rm mod}\ \varphi(m)},&\gcd(a,m)=1\\a^{(b{\rm \ mod}\ \varphi(m))+\varphi(m)},&\gcd(a,m)\ne1,b\ge\varphi(m)\\a^b,&\gcd(a,m)\ne1,b<\varphi(m)\end{cases}\ \ \ \ ({\rm mod}\ m)

    即，若底数和模数互素，可将幂bb降为φ(m)\varphi(m) 否则，若指数比模数大，可将幂bb降为(bmod  φ(m))+φ(m)(b\mod\varphi(m))+\varphi(m) 很简单可以得到，如果模数为质数，则φ(m)=m−1\varphi(m)=m-1，则ab≡ab mod (m−1) (mod m)a^b\equiv a^{b{\rm\ mod}\ (m-1)}\ ({\rm mod}\ m) 实际上，当gcd⁡(a,m)=1\gcd(a,m)=1时，第二项仍成立，这里的意思是优先考虑第一项、如果不互素才考虑第二项；其实可以把gcd⁡()\gcd()限制去掉直接记第二项 即

    ab≡{a(b mod φ(m))+φ(m),b≥φ(m)ab,b<φ(m)\begin{align}&a^b\equiv\begin{cases}a^{(b\ {\rm mod}\ \varphi(m))+\varphi(m)},&b\ge\varphi(m)\\a^b,&b<\varphi(m)\end{cases}\end{align}

  • 证明：

    • 第一项是容易得出的，由欧拉定理，若gcd⁡(a,m)=1\gcd(a,m)=1，则aφ(m)≡1 (mod m)a^{\varphi(m)}\equiv1\ ({\rm mod}\ m) 那么ab≡anφ(m)+(b mod φ(m))≡1n⋅ab mod φ(m)  (mod m)a^b\equiv a^{n\varphi(m)+(b\ {\rm mod}\ \varphi(m))}\equiv1^n·a^{b\ {\rm mod}\ \varphi(m)}\ \ ({\rm mod}\ m)

    • 第二项：因为gcd⁡(a,m)≠1\gcd(a,m)\ne1，将aa拆解为多个质因数的幂的乘积形式，即

      a=∏pi为素数∧pi∣apiri⇒ab=∏pi为素数∧pi∣apib⋅ri\begin{align}a=\prod_{p_i为素数\wedge p_i|a} p_i^{r_i}\Rightarrow a^b=\prod_{p_i为素数\wedge p_i|a} p_i^{b·r_i}\end{align}

      对每一个质因子pip_i：

      • 如果gcd⁡(pi,m)=1\gcd(p_i,m)=1，则由欧拉定理得piφ(m)≡1 (mod m)⇒pib≡pib mod φ(m) (mod m)p_i^{\varphi(m)}\equiv1\ ({\rm mod}\ m)\Rightarrow p_i^{b}\equiv p_i^{b\ {\rm mod}\ \varphi(m)}\ ({\rm mod}\ m)

      • 否则，将mm写成pip_i因子和非pip_i因子的两部分m=s⋅pikm=s·p_i^k，其中k>0k>0 由于ss不是pip_i的幂，即gcd⁡(s,pi)=gcd⁡(s,pik)=1\gcd(s,p_i)=\gcd(s,p_i^k)=1，再次用欧拉定理和欧拉函数的性质得piφ(s)≡1 (mod s)、φ(m)=φ(s⋅pik)=φ(s)φ(pik)p_i^{\varphi(s)}\equiv1\ ({\rm mod}\ s)、\varphi(m)=\varphi(s·p_i^k)=\varphi(s)\varphi(p_i^k)

        因此piφ(m)≡piφ(s)φ(pik)≡1φ(pik) (mod s)p_i^{\varphi(m)}\equiv p_i^{\varphi(s)\varphi(p_i^k)}\equiv1^{\varphi(p_i^k)}\ ({\rm mod}\ s) 两边同乘pikp_i^k，得piφ(m)+k≡pik (mod m)p_i^{\varphi(m)+k}\equiv p_i^k\ ({\rm mod}\ m) 因此pib≡pib−k+k≡pib−k+k+φ(m)≡pib+φ(m) (mod m)p_i^b\equiv p_i^{b-k+k}\equiv p_i^{b-k+k+\varphi(m)}\equiv p_i^{b+\varphi(m)}\ ({\rm mod}\ m)，其中b≥φ(m)b\ge\varphi(m) 于是可以对bb进行变换，得pib−φ(m)≡pib (mod m)p_i^{b-\varphi(m)}\equiv p_i^{b}\ ({\rm mod}\ m)，其中b−φ(m)≥φ(m)b-\varphi(m)\ge\varphi(m)，即b≥2φ(m)b\ge2\varphi(m) 即只有当b≥2φ(m)b\ge2\varphi(m)时，可以降幂；于是幂的最小值范围为[φ(m),2φ(m))[\varphi(m),2\varphi(m)) 即降幂的最小值为(b mod φ(m))+φ(m)(b\ {\rm mod}\ \varphi(m))+\varphi(m)

      结合两种情况(第一种情况可以变成第二种情况的形式)，对aa的任意质因子pip_i，有pib≡pi(b mod φ(m))+φ(m) (mod m)p_i^b\equiv p_i^{(b\ {\rm mod}\ \varphi(m))+\varphi(m)}\ ({\rm mod}\ m)，即pibri≡pi((b mod φ(m))+φ(m))ri (mod m)p_i^{br_i}\equiv p_i^{((b\ {\rm mod}\ \varphi(m))+\varphi(m))r_i}\ ({\rm mod}\ m) 即ab≡a(b mod φ(m))+φ(m) (mod m)a^b\equiv a^{(b\ {\rm mod}\ \varphi(m))+\varphi(m)}\ ({\rm mod}\ m)，原式得证

    • 第三项：既然b<φ(m)b<\varphi(m)了，自然不能降幂了