定理"/>

扩展欧拉定理

扩展欧拉定理

ab≡⎧⎩⎨⎪⎪ab%ϕ(p)           gcd(a,p)=1ab                  gcd(a,p)≠1,b<ϕ(p)ab%ϕ(p)+ϕ(p)    gcd(a,p)≠1,b≥ϕ(p)       (mod p) $$a^b\equiv \begin{cases} a^{b\%\phi(p)}~~~~~~~~~~~gcd(a,p)=1\\ a^b~~~~~~~~~~~~~~~~~~gcd(a,p)\neq1,b&lt;\phi(p)\\ a^{b\%\phi(p)+\phi(p)}~~~~gcd(a,p)\neq1,b\geq\phi(p) \end{cases}~~~~~~~(mod~p)$$

证明转载自

1. 在 a $a$的0$0$次， 1 $1$次，…，b$b$次幂模 m $m$的序列中，前r$r$个数( a0 $a^0$到 ar−1 $a^{r-1}$)互不相同，从第 r $r$个数开始，每s$s$个数就循环一次。
   证明：由鸽巢定理易证。
   我们把 r $r$称为a$a$幂次模 m $m$的循环起始点，s$s$称为循环长度。（注意： r $r$可以为0$0$）
   用公式表述为： ar≡ar+s(mod m) $a^r\equiv a^{r+s}(mod~m)$
2. a $a$为素数的情况
   令m=prm′$m=p^rm'$，则 gcd(p,m′)=1 $gcd(p,m')=1$，所以 pϕ(m′)≡1(mod m′) $p^{\phi(m')}\equiv 1(mod~m')$
   又由于 gcd(pr,m′)=1 $gcd(p^r,m')=1$，所以 ϕ(m′)|ϕ(m) $\phi(m')|\phi(m)$，所以 pϕ(m)≡1(mod m′) $p^{\phi(m)}\equiv1(mod~m')$，
   即 pϕ(m)=km′+1 $p^{\phi(m)}=km'+1$，两边同时乘以 pr $p^r$，得 pr+ϕ(m)=km+pr $p^{r+\phi(m)}=km+p^r$（因为 m=prm′ $m=p^rm'$）
   所以 pr≡pr+s(mod m) $p^r\equiv p^{r+s}(mod~m)$，这里 s=ϕ(m) $s=\phi(m)$
3. 推论： pb≡pr+(b−r)%ϕ(m)(mod m) $p^b\equiv p^{r+(b-r)\%\phi(m)}(mod~m)$
4. 又由于 m=prm′ $m=p^rm'$，所以 ϕ(m)≥ϕ(pr)=pr−1(p−1)≥r $\phi(m)\geq \phi(p^r)=p^{r-1}(p-1)\geq r$
   所以 pr≡pr+ϕ(m)≡pr%ϕ(m)+ϕ(m)(mod m) $p^r\equiv p^{r+\phi(m)}\equiv p^{r\%\phi(m)+\phi(m)}(mod~m)$
   所以 pb≡pr+(b−r)%ϕ(m)≡pr%ϕ(m)+ϕ(m)+(b−r)%ϕ(m)≡pϕ(m)+b%ϕ(m)(mod m) $p^b\equiv p^{r+(b-r)\%\phi(m)}\equiv p^{r\%\phi(m)+\phi(m)+(b-r)\%\phi(m)}\equiv p^{\phi(m)+b\%\phi(m)}(mod~m)$
   即 pb≡pb%ϕ(m)+ϕ(m)(mod m) $p^b\equiv p^{b\%\phi(m)+\phi(m)}(mod~m)$
5. a $a$为素数的幂的情况
   是否依然有ar′≡ar′+s′(mod m)$a^{r'}\equiv a^{r'+s'}(mod~m)$？(其中 s′=ϕ(m),a=pk $s'=\phi(m),a=p^k$)
   答案是肯定的，由2知 ps≡1(mod m′) $p^s\equiv 1(mod~m')$，所以 ps×kgcd(s,k)≡1(mod m′) $p^{s\times \frac{k}{gcd(s,k)}}\equiv 1(mod~m')$，所以当 s′=sgcd(s,k) $s'=\frac{s}{gcd(s,k)}$时才能有 ps′k≡1(mod m′) $p^{s'k}\equiv 1(mod~m')$，此时 s′|s|ϕ(m) $s'|s|\phi(m)$，且 r′=⌈rk⌉≤r≤ϕ(m) $r'=\lceil \frac{r}{k} \rceil\leq r\leq \phi(m)$
   由 r′,s′ $r',s'$与 ϕ(m) $\phi(m)$的关系，依然可以得到 ab≡ab%ϕ(m)+ϕ(m)(mod m) $a^b\equiv a^{b\%\phi(m)+\phi(m)}(mod~m)$
6. a $a$为合数的情况
   只证a$a$拆成两个素数的幂的情况，大于两个的用数学归纳法可证。
   设 a=a1a2,ai=piki $a=a_1a_2,a_i={p_i}^{k_i}$， ai $a_i$的循环长度为 si $s_i$
   则 s|lcm(s1,s2) $s|lcm(s1,s2)$，由于 s1|ϕ(m),s2|ϕ(m) $s1|\phi(m),s2|\phi(m)$，那么 lcm(s1,s2)|ϕ(m) $lcm(s1,s2)|\phi(m)$，所以 s|ϕ(m) $s|\phi(m)$
   r=max(⌈riki⌉)≤max(ri)≤ϕ(m) $r=max(\lceil \frac{ri}{ki} \rceil)\leq max(ri)\leq\phi(m)$
   由 r,s $r,s$与 ϕ(m) $\phi(m)$的关系，依然可以得到 ab≡ab%ϕ(m)+ϕ(m)(mod m) $a^b\equiv a^{b\%\phi(m)+\phi(m)}(mod~m)$
   证毕。