扩展欧拉定理

紫钦 · 2019-06-27 21:29:46 · 个人记录

前言

扩展欧拉定理是欧拉定理的延伸，其适用范围更大，也更常用。

我博客中的一些扩欧题解。

正文

欧拉定理：若 (a,n)=1 ，则 a^{\phi(n)}\equiv1\pmod{n} 。

扩展欧拉定理将欧拉定理扩展到 a,n 不互质的情况：

a^c\equiv \begin{cases}a^{c\mod \phi(n)}\ \ \ \ \ \ \ \ \ ,\gcd(a,n)=1 \\ a^c\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ , \gcd(a,n) \neq 1,c\leqslant\phi(n) \\ a^{(c\mod\phi(n))+\phi(n)},\gcd(a,n)\neq 1,c>\phi(n) \end{cases}\pmod n

考虑到 $c=\phi(n)$ 的情况在第三个式子里会无止境循环，故将其放入第二式。 ## 证明：前两个式子不用证了吧。第三个式子证明如下： + 我们先考虑 $a$ 的一个质因子 $p$ ，试证明：$p^c\equiv p^{(c\mod\phi(n))+\phi(n)},c>\phi(n)\pmod n$ ，不妨设 $n=s\times p^r\ ,\ \gcd(s,p)=1\ ,\ s\geqslant 1\ ,\ r\geqslant 0\ ,\ s,r\in N$ ， + 若 $r=0$ ，由欧拉定理知上式一定成立。 + 若 $r\neq0$ ，那么 $\because\gcd(s,p)=1$ ， $\therefore p^{\phi(s)}\equiv1\pmod s\ ,\ \phi(n)=\phi(s)\times \phi(p^r)$ ， $\therefore p^{\phi(n)}\equiv1\pmod s$ ，则对于 $\forall\ t\in N\ ,\ p^t\equiv p^{t\mod\phi(n)}\pmod s

两边同乘 $p^r$ ，而得到 $\pmod n$ 的形式。

$\therefore p^{t+r}\equiv p^{t\mod\phi(n)+r}\pmod n$ ，

特别的，当 $t=\phi(n)$ 时，有 $p^{\phi(n)+r}\equiv p^r\pmod n$

**需注意， $\phi(n)$ 与 $r$ 是有明确大小关系的。**

$PS.$ 当然你得到了 $p^{t+r}\equiv p^{t\mod\phi(n)+r}\pmod s$ 也是对的，但是没有用。

考察 $\phi(n)$ 与 $r$ 满足的限制条件：

$\phi(n)=\phi(s)\times(p-1)\times p^{r-1}\geqslant p^{r-1}\geqslant2^{r-1}\geqslant r$ ，

当且仅当 $p=2,r=1$ 或 $p=2,r=2$ 时等号成立。

于是 $p^{\phi(n)-r}\geqslant 1$ ,

将上述同余式两边同乘 $p^{\phi(n)-r}$ 得：

$p^{t+\phi(n)}\equiv p^{t\mod\phi(n)+\phi(n)}\pmod n$ ，

$\therefore p^{t+\phi(n)}\equiv p^{(t+\phi(n))\mod\phi(n)+\phi(n)}\pmod n$ ，

令 $c=t+\phi(n)\geqslant\phi(n)$ ，则上式写作：

$p^c\equiv p^{c\mod\phi(n)+\phi(n)}\pmod n\ ,\ c\geqslant\phi(n)$ ；

设 $c_i=i\times\phi(n)+j$ ，其中 $i,j\in N,i\geqslant1,j<\phi(n)$ ，

那么对于任意给定的 $j$ ，有 $p^{c_1}\equiv p^{c_2}\equiv\cdots\equiv p^{c_i}\pmod n$ ，任取其中两项作比较可得：

$p^c\equiv p^{c\mod\phi(n)+k\phi(n)}\pmod n\ ,\ c\geqslant\phi(n),k\in N_+$

我们再考虑 p^k\ ,\ k>1 ，则：
(p^k)^c\equiv p^{kc}\equiv p^{kc\mod\phi(n)+\phi(n)}\pmod n\ ,\ c\geqslant\phi(n)
不妨设 k=i\times\phi(n)+j ，其中 i,j\in N,i\geqslant1,j<\phi(n) ，则有：
p^{kc\mod\phi(n)+\phi(n)}\equiv p^{(k\mod\phi(n))\times(c\mod\phi(n))+((c\mod\phi(n))\times i+k)\times\phi(n)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \equiv p^{(j+i\times\phi(n))\times(c\mod\phi(n))+k\times\phi(n)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \equiv p^{k\times(c\mod\phi(n))+k\times\phi(n)}
对于 \forall\ a\in N_+\ ,\ a=p_1^{k_1}p_2^{k_2}\cdots p_i^{k_i} ，由同余可乘性得：
即 $a^c\equiv a^{c\mod\phi(n)+\phi(n)}\ ,\ c\geqslant \phi(n)$ 。

则扩展欧拉定理得证。

扩展欧拉定理怎么用呢？

若 c\leqslant\phi(n) ，则直接用快速幂计算。

若 c>\phi(n) ，则使用三式将指数变小，再进行快速幂。

扩展欧拉定理有什么用呢？

扩展欧拉定理俗称“降幂大法”，用于处理模意义下的极大指数（如指数塔）形式。

例如求：\underbrace{2^{2^{2^{\cdots}}}}_{total\ \infty}\mod p ，题目详情请见P4139 上帝与集合的正确用法。

（PS. 注意到这是一道紫题，所以你看欧拉函数很有用。）

解：设 f=\underbrace{2^{2^{2^{\cdots}}}}_{total\ \infty} ，若 p=2 ，则直接输出 0 ；

若 p\neq2 ，易知 f>\phi(p) ，

则：f\equiv \begin{cases}2^{f\mod \phi(p)}\ \ \ \ \ \ \ \ \ ,\gcd(f,p)=1 \\ 2^{(f\mod\phi(p))+\phi(p)},\gcd(f,p)\neq 1 \end{cases}\pmod p

若记 f(p) 为 \underbrace{2^{2^{2^{\cdots}}}}_{total\ \infty}\mod p ，

则：f(p)= \begin{cases}2^{f(\phi(p))}\mod p\ \ \ \ \ \ \ ,\gcd(f,p)=1 \\ 2^{f(\phi(p))+\phi(p)}\mod p,\gcd(f,p)\neq 1 \end{cases} ，

由于 \phi(p) 单调递减，故可用递归来解决该问题，边界条件为 f(1)=0 。

结合快速幂，可以迅速解决这道题，复杂度 O(T\times log_2^2p)。

复杂度证明：

序列 p,\phi(p),\phi(\phi(p)),\cdots,1 的长度为 O(log_2p) ，证明来自于 wlp(\in julao) ，\%\%\%\ wlp（附名片JOHNKRAM）。

证明如下：

先给出三个欧拉函数性质（除证明复杂度，好像没其他用）：
1. 除 \phi(1)=1 外， \phi(2k+1) 是偶数 (k\in N) ，归纳法可证：
- 若 2k+1 为质数，则 \phi(2k+1)=2k 为偶数；
  
  同理若 P 为质数，由 \phi(P^k)=P^{k-1}\times(P-1)\ , k>1 ，知 \phi(P^k) 必然是偶数。
- 若 2k+1 不是质数，不妨设 2k+1=P_1^{q_1}P_2^{q_2}\cdots P_i^{q_i} ，
则\phi(2k+1)=\phi(P_1^{q_1})\phi(P_2^{q_2})\cdots \phi(P_i^{q_i}) 为偶数。
1. 除 \phi(2)=1 外， \phi(2k) 是偶数 (k\in N) ，归纳法可证：
- 若 k 为奇数，则 \phi(2k)=\phi(2)\phi(k)=\phi(k) ，由上一条知此时 \phi(2k) 为偶数。
- 若 k 为偶数，则 \phi(2k)=2\times\phi(k) ，显然 \phi(2k) 是偶数。
1. 由上述三个性质知，序列 $p,\phi(p),\phi(\phi(p)),\cdots,1$ 的长度最大为 $log_2p$ 。
```cpp #include<cstdio> #include<cstdlib> using namespace std; namespace Qza{ #define Maxn 10000007 int T,P; int phi[Maxn],prime[Maxn],F[Maxn]; void get_phi() { static int cnt=0; long long k=0ll; phi[1]=1; for(long long i=2ll;i<=Maxn;++i) { if(!phi[i]) phi[i]=i-1, prime[++cnt]=i; for(int j=1;j<=cnt && (k=i*prime[j])<=Maxn;++j) { if(i%prime[j]) phi[k]=phi[i]*(prime[j]-1); else {phi[k]=phi[i]*prime[j]; break;} } } } long long fastpow(long long a,int b,int p) { long long ans=1ll; while(b) { if(b&1) ans=(ans*a)%p; a=a*a%p; b>>=1; } return ans; } int f(int p) { if(F[p]) return F[p]; if(p==1 || p==2) return 0; // p==2 特判。 if(phi[p]==p-1) { // p 为质数。 // 不要写作 phi[p]=p-1 !!! return F[p]=fastpow(2ll,f(phi[p]),p); } return F[p]=fastpow(2ll,f(phi[p])+phi[p],p); } void main() { get_phi(); scanf("%d",&T); do{ scanf("%d",&P); printf("%d",f(P)); putchar('\n'); // 记得回车 !!! }while(--T); return ; } } int main() { Qza::main(); return 0; } ```

例题

P5091 【模板】欧拉定理。

P3934 Nephren Ruq Insania 。

CF906D Power Tower 。

P3747 [六省联考2017]相逢是问候。