Re：从零开始的同余问题
同余
在开始前必须要说明，涉及同余的变量和参量一般都为整数或正整数。
-
同余的定义
对于
a,b\in\mathbb{Z} ，若a 、b 除以p 所得的余数相等，则称a 和b 对模p 同余，也称a 和b 在模p 意义下相等。定义 “
≡ ” 为同余符号，注意同余符号\equiv 与相等符号= 的区别。有了同余符号后，我们将
a 和b 对模p 同余记作：a \equiv b \pmod{p} ，上式就叫同余式。 -
同余的基本性质
为什么要将模运算单独列出，并称其为同余呢？
原因在于同余满足诸多性质，下面给出同余的基本性质，它们与等式的基本性质有很大相似之处：
1. 同加性：若 $a\equiv b\pmod{p}$，则 $a+k\equiv b+k\pmod{p} - 同乘性：若
a\equiv b\pmod{p} ，则ak\equiv bk\pmod{p} - 同幂性：若
a\equiv b\pmod{p} ，则a^n\equiv b^n\pmod{p} - 自反性：
a\equiv a\pmod{p} - 对称性：若
a\equiv b\pmod{p} ，则b\equiv a\pmod{p} - 传递性：若
a\equiv b\pmod{p} ，且b\equiv c\pmod{p} ，则a\equiv c\pmod{p}
显然，若
a\equiv b ，那么a/n\equiv b/n 不一定成立。只有当
n\mid a,n\mid b ，且(n,p)=1 时，上式成立。证明：
令
a=xn,b=yn xn\equiv yn \pmod {p} xn-yn \equiv 0\pmod {p} n(x-y)\equiv 0\pmod {p} 因为
(n,p)=1 ，所以n \not\equiv 0 \pmod {p} ，所以x-y\equiv0\pmod {p} 。那就有：
x\equiv y \pmod {p} ，证毕。 - 同乘性：若
拓展欧几里得算法
首先我们知道，朴素欧几里得算法的原理是：
-
引理
1 ： -
证明：
对
b 的取值情况进行讨论。-
当
b=0 时：这是朴素欧几里得算法的最后一步，即
gcd(a,b)=a 。那么就有：
a*1+b*0=a ，此时x=1 ，y=0 。 -
当
b\ne0 时：假设已求出
gcd(b,a \bmod b) 的一组解x_2 和y_2 。那么就有：
b*x_2+(a \bmod b)*y_2=gcd(b,a \bmod b)=gcd(a,b) 。我们知道：
a \bmod b=a-\lfloor \frac ab\rfloor*b ，由于在\rm C++ 中自动向下取整，于是下文默认\frac ab=\lfloor \frac ab \rfloor 。所以：
b*x_2+(a-\frac ab*b)*y_2=gcd(a,b) 。拆开括号得：
b*x_2+a*y_2-\frac ab*b*y_2=gcd(a,b) 。整理得：
a*y_2+b*(x_2-\frac ab*y_2)=gcd(a,b) 。那我们便得到方程
ax+by=gcd(a,b) 的一组解：x=y_2 ，y=x_2-\frac ab*y_2 。
利用数学归纳法便可知引理成立（
b=0 时成立，那么b=0 的上个状态会成立，上上个状态也会成立，以此类推），那么拓展欧几里得算法的递归过程也是成立的。 -
于是便可得到快速求解
完全看懂上述推导过程就来写模板练手吧 ~
注意函数内引用，代码如下：
#include<bits/stdc++.h>
using namespace std;
int a,b,x,y;
void exgcd(int a,int b,int &x,int &y){
if(!b){
x=1;
y=0;
return ;
}
exgcd(b,a%b,y,x); //x1=y2,y1=x2,y1 之后再处理
y=y-a/b*x; //y1=x2-a/b*y2
}
int main()
{
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<' '<<y;
return 0;
}非常简短，这就是数论的魅力 ~
不定方程
接上文，我们已经知道不定方程：
当然，该不定方程可能无解，下面介绍判断是否有解的裴蜀定理。
-
裴蜀定理
定理
1 ：**证明**： 令 $d=gcd(a,b)$。 * 若 $d\mid c$ ： 则有 $\frac adx+\frac bdy=\frac cd$。 因为 $gcd(\frac ad,\frac bd)=1$，所以不妨丢掉 $\frac cd$，先求 $\frac adx^\prime+\frac bdy^\prime=gcd(\frac ad,\frac bd)$ 的解。由 $\rm {exgcd}$ 可知，上述方程一定存在整数解。 等式两边同时乘 $c$ 可得：$c*\frac adx^\prime+c*\frac bdy^\prime=c$。 整理得：$a*\frac cdx^\prime+b*\frac cdy^\prime=c$。 将 $\frac cdx^\prime,\frac cdy^\prime$ 视作整体，那便得到原方程的一组整数解：$x=\frac cdx^\prime,y=\frac cdy^\prime$。 * 若 $d\nmid c$： 先列出：$\frac adx+\frac bdy=\frac cd$。 由 $\rm {gcd}$ 的性质知：$\frac ad,\frac bd \in \mathbb{Z}$，而 $\frac cd \notin \mathbb{Z}$。 因此原方程无整数解。 -
不定方程通解
我们已求出原方程的一组整数解
x_*,y_* ，先考虑求离x_*,y_* 最近的一组解x_1,y_1 。首先有：
ax_*+by_*=c 。设
k\in \mathbb{Q} ，在等式左边加上再减去kab ，等式依然成立。整理后得：
a(x_*+kb)+b(y_*-ka)=c 那么就有：
x_1=x_*+kb,y_1=y_*-ka 。现在的问题是求出
k ，使得ka,kb\in \mathbb{Z} 且最小。经过尝试发现，当
k=\frac 1{gcd(a,b)} 时满足条件，这利用了gcd 的性质，即两数同时除以它们的gcd 后互质。那么将
k 代入得：x_1=x_*+ka=x_*+\frac a{gcd(a,b)},y_1=y_*+kb=y_*-\frac b{gcd(a,b)} 。以此类推，
x_i,x_{i-1} 之间也一定相差ka ，y_i 同理。于是通解公式呼吁而出：
\begin{cases}x=x_* \pm s*\frac a{gcd(a,b)}\\y=y_* \mp s*\frac b{gcd(a,b)} \end{cases} 其中
s\in\mathbb{Z} 。 -
P5656 二元一次不定方程
真的是一道毒瘤模板题啊，很容易把自己绕进去，
尤其是像我这样不仔细看题的人。结合上文，已知不定方程的一组特解，难点在于求其正整数解数量、正整数解中最小、最大的
x,y 。注意到通解的特性：两数中一数增大则另一数减小。
我们不妨求出
x 的最小正整数解。此时如果y\le0 ，那么就不存在正整数解，因为y 再大x 就不是正整数了。如果y>0 ，那么此时的y 就是正整数解中最大的。同样的道理，我们在求
y 最小时顺带求出x 最大。有了正整数解中
x 的上下界，那么正整数解数目s=\frac {x_{max}-x_{min}}{c^\prime}+1 ，其中c^\prime=\frac {c}{gcd(a,b)} 。问题解决，代码放这。
线性同余方程
-
定义
形如：
ax\equiv b\pmod {p} 的一次同余方程，我们称之为线性同余方程。 -
解法
观察方程，可知：
p\mid ax-b 。于是将其化为不定方程：ax-py=b 。为了方便表示，此处的
y 取相反数：ax+py=b 。令
d=gcd(a,p) ，解得：x_i=x_0+i*\frac pd 。显然
x_i 的取值需要对p 取模，而我们想知道取模后有多少不同取值，此时需借助定理：-
定理
1 ： -
证明：
已知
x_i=x_0+i*\frac pd 。由于
\frac pd≥1 ，所以当0≤i<d 时，0≤x_i<p ，且x_i 互不相同。因此，原方程恰有
d 个取p 不同余的整数解。至于无解的情况，化为不定方程易知。
-
乘法逆元
众所周知，除法是乘法运算的逆运算，用于抵消乘法，而除以一个数相当于乘以这个数的倒数。
同余问题中，求倒数是很有价值的。假如要求
但是同余式不满足同除性，因此取倒数就不仅仅是
于是便诞生了 乘法逆元 这一分块。
-
定义
对于
a\in\mathbb{Z} ，若有x\in\mathbb{Z} 使得：ax\equiv 1 \pmod p ，则称x 是a 在模p 意义下的逆元。 -
线性同余方程
回顾线性同余方程
ax\equiv b \pmod p 。实际上，逆元的定义式就是线性同余方程
b=1 的情况。然后根据线性同余方程的定理，逆元有解，当且仅当
gcd(a,p) \mid 1 ，也就相当于a,p 互质，同时逆元对p 取余的值恰好为1 ，也就是说求出方程任意一组解并取模即可。那用
\rm {exgcd} 求解便可得到特解，问题解决（求通解套公式即可）。 -
欧拉定理
定理
1 ：若
a,p 互质，则有a^{\phi(p)}\equiv1\pmod p 。证明：
定义
t_1,t_2...t_{\phi(p)} 是模p 的一个简化剩余系，则at_1,at_2...at_{\phi(p)} 也是模p 的一个简化剩余系。为啥呢，不妨分为两部分分析：
-
互质：
因为
t_i 与p 互质，a 与p 互质，所以at_i 也与p 互质。 -
不重复：
考虑反证法。
假设有
at_i\equiv at_j\pmod p ，则变式后得a(t_i-t_j)\equiv 0\pmod p 。这代表
p\mid a(t_i-t_j) 。又因为
p\nmid a ，所以p\mid (t_i-t_j) 。可是
t_i,t_j<p ，所以t_i-t_j<p ，p\nmid (t_i-t_j) ，矛盾，假设不成立。因此，
t_1,t_2...t_{\phi (p)} 和at_1,at_2...at_{\phi(p)} 都是模p 的一个简化剩余系。所以
\forall i,t_i\equiv at_i 。所以
\prod\limits_{i=1}^{\phi(p)}t_i\equiv \prod\limits_{i=1}^{\phi(p)}at_i \pmod p 。所以
\prod\limits_{i=1}^{\phi(p)}t_i\equiv a^{\phi (p)}\prod\limits_{i=1}^{\phi(p)}t_i \pmod p 。化简后可得
a^{\phi(p)}\equiv 1\pmod p ，证毕。
-
-
费马小定理
定理
2 ：若
p 为质数，则对\forall a\in \mathbb{Z} ，都有a^{p-1}\equiv 1 \pmod p 。证明
1 ：由欧拉定理可知：
a^{\phi(p)}\equiv 1\pmod p ，又因为p 为质数，所以\phi(p)=p-1 ，那便有a^{p-1}\equiv 1\pmod p 。证明
2 ：好多啊，
其实是早就写了不想删。我们定义两个集合：
$T_2$ 的所有元素为 $T_1$ 所有元素模 $p$ 后的值。 * **引理 $1$**： 已知 $a,p\in\mathbb{Z}$ 且 $gcd(a,p)=1$。那么对于任意整数 $k_i,k_j$，如果 $k_ia\equiv k_ja\pmod {p}$，那么就有 $k_i\equiv k_j \pmod {p}$。 * **证明**： 由于 $p$ 为质数，显然 $gcd(a,p)=1$。 回顾同余的基本性质，易知：$\frac {k_ia}a\equiv\frac {k_ja}a\pmod {p}$，那么便有 $k_i\equiv k_j \pmod {p}$。 假设 $T_2$ 中存在两个相同元素，也就是 $k_ia\equiv k_ja \pmod {p}$，由引理 $1$ 可知 $T_1$ 中一定存在 $k_1= k_2 \pmod {p}$，这与定义矛盾，假设不成立。 因此 $T_2$ 所有元素互不相同。又因为 $T_2$ 恰有 $p-1$ 个元素。所以 $T_2=\{1,2,3...p-1 \}$，每个元素可表示为 $k_i$。 由 $T_1,T_2$ 的定义知，对于任意 $k_i$ 都有 $k_i\equiv k_ia\pmod {p}$。 也就是： $\prod\limits_{i=1}^{p-1}k_i\equiv \prod\limits_{i=1}^{p-1}k_ia \pmod{p}$。 即：$(p-1)!\equiv a^{p-1}*(p-1)! \pmod {p}$。 化简后便是 $a^{p-1}\equiv 1 \pmod {p}$，证毕。 利用费马小定理，可知 $a^{-1}\equiv a^{p-2} \pmod {p}$。 那么直接用快速幂求逆元即可。 -
递推式求逆元
可在
O(n) 的时间复杂度内，求出1 ~n 在模p 意义下的逆元。问题：
已知
1 ~i-1 的逆元，求i 的逆元。递推式推导：
设
a=\lfloor \frac pi \rfloor,k=p \bmod i 。那就有：
a*i+k\equiv 0 \pmod p 。两边同时乘
k^{-1}*i^{-1} 可得：a*k^{-1}+i^{-1}\equiv 0\pmod p 。移项后便得到递推式：
i^{-1}\equiv -a*k^{-1} \pmod p 。
同余方程组
-
定义
有两个正整数数组
a_1,a_2...a_n 和m_1,m_2...m_n 。那么它们的同余方程组便为：
\begin{cases} x\equiv a_1 \pmod {m_1}\\x\equiv a_2 \pmod {m_2} \\.....\\x\equiv a_n \pmod {m_n}\end{cases} 是不是很像小奥的余数问题？没错，但现在它拓展为
n 个同余方程组，我们用同余方面的知识来分析它。-
引理
1 ：同余方程组若有解
x ，则通解为x+i*lcm(m_1,m_2...m_n) ，其中i\in\mathbb{Z} 。 -
简要证明：
令
M=lcm(m_1,m_2...m_n) ，显然对于\forall m_i,M\equiv 0 \pmod{m_i} 。那么对于任意
i ，在同余式左边加上M 后仍然成立，即：x+M\equiv a_i\pmod {m_i} 。所以正确性得到了保证。又因为
M 是m_1,m_2...m_n 的所有公倍数中最小的，而x 加上一个不是所有m 的公倍数的数后就没有上述推导过程，显然会使方程组不成立。因此通解为x+i*M 时才不会漏解少解，证毕。
-
-
中国剩余定理
老祖宗的智慧，给出了
m_i 两两互质的情况下的特殊解。-
定理
1 ：若
m_i 两两互质，则令M=\prod\limits_{i=1}^{n},M_i=\frac M{m_i} ，t_i 是M_it_i \equiv 1\pmod {m_i} 的一个解（逆元）。则上述方程组的解为：
x=\sum\limits_{i=1}^{n} a_iM_it_i ，且在模M 意义下有唯一解。 -
证明：
因为
M_i 是除m_i 外所有m 的倍数，因此有\forall j \neq i,a_iM_it_i\equiv 0 \pmod {m_j} 。注意到
M_it_i \equiv 1\pmod {m_i} ，两边同时乘上a_i 得：a_iM_it_i \equiv a_i \pmod {m_i} 。令
x=\sum\limits_{i=1}^{n} ，那么对于任意i ，都有x \equiv a_i \pmod {m_i} 。这可以理解为：对于任意
i ，x 中都存在对应的a_iM_it_i 使得方程组成立，同时x 中除a_iM_it_i 外的其它部分又不影响同余式成立。于是我们得到一组特解。注意到
M=lcm(m_1,m_2...m_n) ，借助引理1 ，就可解释所有x 为何在模M 意义下值是唯一的。证毕。 -
另外一种理解方式：
参考自 yyc 巨佬的证明，更直观地揭示了其底层原理，而且码量极少。
但是大佬的思路不太好表达啊QwQ考虑将方程组两两合并：
\begin{cases} x\equiv a_i \pmod {m_i}\\x\equiv a_{i+1} \pmod {m_{i+1}}\end{cases} 利用构造法，令
x=a_im_{i+1}+a_{i+1}m_i 。好处在于构造了分别为
m_i,m_{i+1} 的倍数的两部分，使得x 模m_i 得a_im_{i+1} ，模m_{i+1} 后得a_{i+1}m_i 。唯一的问题便是抵消掉
m_i,m_{i+1} 。同样的，分为两部分，对于抵消m_i 需要修改a_{i+1}m_i ，利用逆元的知识，使其乘上m_i 在模m_{i+1} 意义下的逆元即可抵消m_i 。对于抵消m_{i+1} 也是同理，乘上m_{i+1} 在模m_i 意义下逆元即可。于是
x=t_ia_im_{i+1}+t_{i+1}a_{i+1}m_i ，其中t 表示逆元。当
1 ~i-1 部分合并后，方程组1 ~i-1 都可成立，那么模数便是\prod\limits_{i=1}^{n}m_i ，这是给下次合并加上限制。所以怎么推递推式呢？根据上面内容推导即可。
假设已求出
1 ~i-1 的解x_1 ，M=\prod\limits_{j=1}^{i-1}m_j ，现在要加上方程组x\equiv a_i\pmod {m_i} 。那么
x=x_1m_i+a_iM ，这样分别模M,m_i 后可得前半、后半部分。之后就是要去掉前半后半部分的
m_i,M ，令m_it_1\equiv 1\pmod {M} ，Mt_2\equiv 1\pmod {m_i} 。分别乘上上
t_1,t_2 得：x=t_1x_1m_i+t_2a_iM 。至于初始化，令
M=1,x_1=0 ，代入上式后发现刚好满足第一个同余式。到此结束。
-
-
拓展中国剩余定理
当
m_i 不满足两两互质时，朴素中国剩余定理就无法使用了，因为逆元部分需满足两数互质。那么考虑两两合并，假设已知前
i-1 个方程组的特解x^\prime_* ，现在求前i 个方程的特解x_* 。令：
M_i=lcm(m_1,m_2...m_i) 由引理
1 知，前i-1 个方程组的通解是x^\prime_s=x^\prime_*+s*M_{i-1} ，那么x_* 必然是这些解中的一个。于是问题转化为求解：
x^\prime_*+s*M_{i-1}\equiv a_i\pmod {m_i} 。这就很眼熟了，再转变一次：
s*M_{i-1}\equiv a_i-x^\prime_*\pmod {m_i} 。其中只有
s 为未知数，所以直接求解上述线性同余方程即可。需要注意的是，该同余方程组不一定有解，每次用
\rm{exgcd} 判断是否有解即可。总的来说，解
n 次线性同余方程即可得出整个方程组的解。
高次同余方程
-
定义
-
解法
考虑
\rm{BSGS} 算法求解。-
引理
1 ：a^{i}\equiv a^{i\bmod\phi(p)} \pmod {p} -
证明：
由欧拉定理知：
a^{\phi(p)}\equiv 1\pmod p 。所以
a^{k\phi(p)}\equiv 1\pmod p ，其中k\in\mathbb{Z} 。所以若有
t*a^{k\phi(p)}\equiv 1\pmod p ，则t\equiv 1\pmod p ，其中t 是a^{k\phi(p)} 在模p 意义下的逆元。所以
a^{i \bmod \phi(p)}\equiv a^{i-k\phi(p)}\equiv \frac {a^i}{a^{k\phi(p)}}\equiv a^it\equiv a^i \pmod p ，证毕。
由引理
1 知，a^i\equiv a^{i\bmod \phi(p)} 。因为\phi(p)\le p-1 ，所以我们只需考虑1\le x\le p 的情况即可。那么设
m=\sqrt p,i,j\in\mathbb{Z} ，其中0\le i\le m,0\le j \le m-1 ，则x=i*m-j ，原方程便可表示为：a^{i*m-j}\equiv b\pmod p 。整理得：
\frac {a^{i*m}}{a^j}\equiv b\pmod p \to {a^{m}}^{i}\equiv b*a^{j}\pmod p 。那么预处理
b*a^j ，将其插入\rm {Hash} 表中。然后枚举i ，判断\rm {Hash} 表中是否存在任意b*a^{j} 使得等式成立即可，其中，若已知i,j ，则求出x 并更新结果即可。 -
-
exBSGS
放宽限制，若
a,b,p 为任意整数、不一定有a,p 互质时，则需使用拓展\rm{BSGS} 解决。-
引理
1 ：若有
a\equiv b\pmod p ，令d=gcd(a,p) ，且d\mid b ，则有\frac ad\equiv \frac bd\pmod {\frac pd} 。 -
证明：
移项得 $\frac add-\frac bdd\equiv 0\pmod {\frac pdd}$。 所以有 $t\in\mathbb{Z},t{\frac pdd}=\frac add-\frac bdd$。 同时除以 $d$ 得 $t\frac pd\equiv \frac ad-\frac bd$。 所以有 $\frac ad-\frac bd\equiv 0\pmod {\frac pd}$。 那么 $\frac ad\equiv \frac bd\pmod \frac pd$。 证毕。
考虑通过一系列除法，使其化为朴素
\rm{BSGS} 。具体步骤：
令
d_1=gcd(a,p) 。那么原方程可变化为
\frac {a^x}{d_1}\equiv \frac b{d_1}\pmod {\frac p{d_1}} 。以此类推，
d_i=gcd(a,\frac p{\prod\limits_{j=1}^{i-1} d_j}) ，不断除以d_i 直到d_{k+1}=1 。注意中途若有d_i\nmid b 则无解。令
D=\prod\limits_{i=1}^{k}d_i 。有些抽象，那么经过
k 次操作后，方程的具体情况便是：\frac {a^x}{D}\equiv \frac bD\pmod {\frac pD}\to a^{x-k}\frac {a^k}D\equiv \frac bD\pmod \frac{p}{D} 这样一看舒服多了。此时满足
a,\frac pD 互质，那便有\frac {a^k}D,\frac pD 互质。于是可使用逆元消掉方程左边的
\frac {a^k}D 。令t\in\mathbb{Z},t\frac {a^k}D\equiv 1\pmod \frac pD ，则方程最终是这个样子：a^{x-k}\equiv t\frac bD\pmod {\frac pD} 预处理结束，接下来用朴素
\rm{BSGS} 解上述方程即可。 -
拓展欧拉定理
-
定理
1 ：若有
a,b,p\in\mathbb{Z} ，且b\ge \phi (p) ，则有a^b\equiv a^{(b\bmod \phi(p))+\phi(p)}\pmod p -
证明：
考虑先证明对于
p 的一个质因子q 满足上式。那便有
p=sq^r,s\in \mathbb{Z},r\in \mathbb{Z} ，并满足s,q 互质，这一点不证。由于
gcd(s,q)=1 ，所以由欧拉定理知q^{\phi(s)}\equiv1\pmod s 。由于欧拉函数是积性函数，所以
sq^r=p\to \phi(s)\phi(q^r)=\phi(p) 。关键一步，因为
q^{\phi(s)}\equiv 1\pmod s ，所以有{q^{\phi(s)}}^{\phi(q^r)}\equiv 1\to q^{\phi(s)*\phi(p^r)}\equiv 1\to q^{\phi(p)}\equiv 1\pmod p 。那么显然也有
q^{kr}\equiv 1\pmod p 。于是可得出：对于任意非负整数
x ，都有q^{x+kr}\equiv q^x\pmod p 。而因为
b\ge\phi(p) ，所以一定存在b=x+kr,x\in\mathbb{Z} ，并且满足2\phi(p)>x\ge\phi(p) 。根据上面的推导，可知
q^{b}\equiv q^{x+kr}\equiv q^x\pmod p 。又因为当
2\phi(p)>x\ge\phi(p) 时，有x-\phi(p)=x\bmod \phi(p) 。而且由
b=x+kr 知b\equiv x\pmod p ，所以有b\bmod \phi(p)=x-\phi(p) 。所以
b\bmod \phi(p)+\phi(p)=x 。所以
q^x\equiv q^{b\bmod \phi(p)+\phi(p)} ，那就得到q^{b}\equiv q^{b\bmod \phi(p)+\phi(p)} 。那么对于
q^{w},w\in\mathbb{Z} （需满足q^w\mid p ），也有q^{w}\equiv {q^{w}}^{b\bmod \phi(p)+\phi(p)} ，证法相似故不展示。令
a=a_1*a_2 ，其中gcd(a_2,p)=1,a_1=\prod {q_i}^{a_i} ，即a_1 所有的质因数都是p 的质因数。（a_i 是q_i 的次数而不是a^b 中的a ）对于
a_1 ，已经证明\forall{{q_i}^{a_i}}^{b}\equiv {{q_i}^{a_i}}^{b\bmod \phi(p)+\phi(p)}\pmod p ，又因为{a_1}^{b}\equiv \prod {q_i}^{a_i} \pmod p ，进而有{a_1}^b\equiv {a_1}^{b\bmod \phi(p)+\phi(p)}\pmod p 。对于
a_2 ，由欧拉定理推论知{a_2}^{b}\equiv {a_2}^{b\bmod \phi(p)}\pmod p ，又因为{a_2}^{\phi(p)}\equiv 1\pmod p ，所以也有{a_2}^{b}\equiv {a_2}^{b\bmod \phi(p)+\phi(p)}\pmod p 。综上，
a^b\equiv {a_1}^b*{a_2}^b\equiv {a_1}^{b\bmod \phi(p)+\phi(p)}*{a_2}^{b\bmod \phi(p)+\phi(p)}\equiv a^{b\bmod \phi(p)+\phi(p)}\pmod p ，证毕。
不管那么多，拓展欧拉定理给予我们将
第一种情况就是朴素欧拉定理，不再赘述。
而第二种情况则代表