裴蜀定理 & 扩展欧几里得 & 中国剩余定理 & 扩展中国剩余定理 学习笔记
jiezecheng
·
2025-11-15 17:25:02
·
算法·理论
裴蜀定理
定理内容：
对于方程（其中 a,b 是整数）：
ax+by=\gcd(a,b)
一定有解。
当且仅当方程 ax+by=c 中 c 为 \gcd(a,b) 的倍数时，方程有整数解。
欧几里得算法
内容（其中 \bmod 表示取模）：
\gcd(a,b)=\gcd(b,a \bmod b)
扩展欧几里得算法
在欧几里得算法的基础上，扩展欧几里得算法不仅能求 a,b 的 \gcd ，还能求不定方程 ax+by=\gcd(a,b) 的一组特解。
终止情况：当 b=0 时，\gcd(a,b)=a ，方程的解为 x=1,y=0 。
递归求解 \gcd ：递归求解。
我们运行欧几里得算法的过程如下：
\begin{matrix}
a& b & x& y\\
a_2& b_2 & x_2& y_2\\
\vdots & \vdots & \vdots & \vdots \\
a_5& b_5 & x_5& y_5\\
a_6& b_6 & x_6& y_6\\
\end{matrix}
其中最后一行是已经求解完成的答案（其中 b_6=0,x_6=1,y_6=0 ，其余的 x,y 都未知），那么我们已知：
a_6x_6+b_6y_6=g_6
我们要求：
满足
a_5x_5+b_5y_5=g
的整数 x_5,y_5 。
根据欧几里得算法的递归过程，我们知道：
\left\{\begin{matrix}
a_6=b_5\\
b_6=a_5\bmod b_5=a_5-\left \lfloor \frac{a_5}{b_5} \right \rfloor\times b_5
\end{matrix}\right.
带入并化简：
a_5y_6+b_5(x_6-y_6\times \left \lfloor \frac{a_5}{b_5}\right \rfloor )=g
所以答案显而易见。
代码
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int tx,ty;
int tg=exgcd(b,a%b,tx,ty);
x=ty;
y=tx-ty*(a/b);
return tg;
}求 ax+by=c 的解
我们已经求出了方程 ax+by=\gcd(a,b) 的一组特解 x^*,y^* 。
解决 ax+by=c 的一组特解，我们已经知道 c 为 \gcd(a,b) 的倍数（裴蜀定理），即 c=k\gcd(a,b) ，其中 k\in \mathbb{Z} 。
那么 ax+by=c 的一组特解为 kx^*,ky^* 。
扩展欧几里得求逆元
求 a 在模 b 意义下的逆元即求方程
ax\equiv 1\pmod b
回忆一下取模运算，方程变为
ax-by=1
的正整数解中的 x 的取值，用扩展欧几里得算即可。
并且，我们通过裴蜀定理可知：
只有当模数 p 与 a 互质时 a 在模 p 意义下存在逆元。
扩展欧几里得求通解
首先考虑方程 ax+by=0 的解（不妨令 g=\gcd(a,b) ）：
显然其中一个解为 x=b,y=-a ，显然 x=kb,y=-ka 其中 k\in \mathbb{Z} 都是这个方程的解。
但是注意这并不是通解，因为这个解没有覆盖全部的解，不过如果想要覆盖全部的解只需要让 x=k\frac{b}{g},y=-k\frac{a}{g} 其中 k\in \mathbb{Z} 。这就是 ax+by=0 的通解啦。
考虑 ax+by=c 的通解。
我们已经知道一组 x^*,y^* 满足 ax^*+by^*=c 。也知道 ax+by=c 的通解，我们只需要让两个方程相加，可得：
a(x^*+k\frac{b}{g})+b(y^*-k\frac{a}{g})=c \qquad k\in \mathbb{Z}
那么显然通解是 x^*+k\frac{b}{g} 和 y^*-k\frac{a}{g} 。
中国剩余定理
中国剩余定理（Chinese remainder theorem），又名孙子定理，主要用于解同余方程组。
最早，在《孙子算经》中有这样一个问题：
:::info[原文]
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？用白话描述就是，现在有一个数不知道是多少，只知道这个数除以 3 余 2 ，除以 5 余 3 ，除以 7 余 2 ， 问这个数是多少？
:::
求满足如下方程组的最小正整数 x 。
\left\{\begin{matrix}
x\equiv 2\pmod3\\
x\equiv 3\pmod5\\
x\equiv 2\pmod7\\
\end{matrix}\right.
如果你试一下可以发现答案是 23 。
这个定理阐述了如何解如下的同余方程组：
\left\{\begin{matrix}
x\equiv a_1\pmod {m_1}\\
x\equiv a_2\pmod {m_2}\\
\vdots \\
x\equiv a_n\pmod {m_n}\\
\end{matrix}\right.
其中所有 m 两两互质 。
这个方程组在模 M=m_1m_2m_3\dots m_n 意义下是有唯一解的。
那么究竟怎么解出这个解呢。
首先考虑如果这个方程组只有一个方程，即解 x\equiv a_1\pmod {m_1} 。显然，答案是 a_1 。
尝试将一个方程拓展到两个方程，即将两个方程合并为一个 。
\left\{\begin{matrix}
x\equiv a_1\pmod {m_1}\\
x\equiv a_2\pmod {m_2}\\
\end{matrix}\right.
将同余式换为等式：
\left\{\begin{matrix}
x=a_1+k_1m_1\\
x=a_2+k_2m_2\\
\end{matrix}\right.
联立：
a_1+k_1m_1=a_2+k_2m_2
变形：
k_1m_1-k_2m_2=a_2-a_1
（由于 m 两两互质，则这个方程一定有整数解（裴蜀定理））
使用扩展欧几里得解出特解 k_1^*,k_2^* 。
求出 x 的通解 k_1^*+km_2\quad k\in \mathbb{Z} ，带回我们的原式 x=a_1+k_1m_1 ：
\begin{align}
x & = a_1+k_1m_1\\
x & = a_1+(k_1^*-km_2)m_1\qquad k\in \mathbb{Z}\\
x & = a_1+k_1^*m_1-km_1m_2\qquad k\in \mathbb{Z}\\
\end{align}
诶！x=a_1+k_1^*m_1-km_1m_2\qquad k\in \mathbb{Z} 不正好是同余方程的等式写法吗！
将其换为 x\equiv a_1+k_1^*m_1\quad \pmod {m_1m_2} 。
好的，现在我们成功地将两个同余方程转化为了一个！
我们只需要每次将两个方程转化为一个，就可以最终只剩下一个方程啦！
代码
pair<int,int> Merge(int a1,int m1,int a2,int m2){
auto [k1,k2]=solve(m1,m2,a2-a1);
int nwm=m1*m2;
int nwa=(a1+(k1*m1)%nwm+nwm)%nwm;
nwa=(nwa%nwm+nwm)%nwm;
return make_pair(nwa,nwm);
}P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪
扩展中国剩余定理
这个定理阐述了如何解如下的同余方程组：
\left\{\begin{matrix}
x\equiv a_1\pmod {m_1}\\
x\equiv a_2\pmod {m_2}\\
\vdots \\
x\equiv a_n\pmod {m_n}\\
\end{matrix}\right.
等一下，这和中国剩余定理有什么区别？
注意，此时 m 不一定两两互质 。
但是其实没什么区别。
从哪一步开始不一样的呢？
书接上回，我们已经把原式变为了：
k_1m_1-k_2m_2=a_2-a_1
但是此时 m_1,m_2 并不一定互质，所以这个方程不一定有解，只有当 a_2-a_1 是 \gcd(m_1,m_2) 的倍数时，这个不定方程才有解（裴蜀定理）。
如果有解的话 ：
使用扩展欧几里得解出特解 k_1^*,k_2^* 。
记 g=\gcd(m_1,m_2) 。
解出 k_1 通解 k^*+k\frac{m_2}{g} ，带回。
\begin{align}
x & = a_1+k_1m_1\\
x & = a_1+(k_1^*-k\frac{m_2}{g})m_1\qquad k\in \mathbb{Z}\\
x & = a_1+k_1^*m_1-k\frac{m_1m_2}{g}\qquad k\in \mathbb{Z}\\
\end{align}
别忘了 m_1m_2=\gcd(m_1,m_2)\times \text{lcm}(m_1,m_2) 。
所以原来的两个方程变为了一个同余方程：
x\equiv a_1+k_1m_1\quad \pmod {\text{lcm}(m_1,m_2)}
只需要接下来一步一步将若干个方程转化为同一个方程就可以啦。
此时这个方程最终的模数为 M=\text{lcm}(m_1,m_2,\dots ,m_n) 。
注意：如果中途有任何一步是无解的，那么整个方程组都无解 。
代码
pair<int,int> Merge(int a1,int m1,int a2,int m2){
auto [k1,k2]=solve(m1,m2,a2-a1);
int gm=__gcd(m1,m2);
int nwm=m1/gm*m2;
int nwa=((a1+(k1*m1)%nwm)%nwm+nwm)%nwm;
nwa=(nwa%nwm+nwm)%nwm;
return make_pair(nwa,nwm);
}P4777 【模板】扩展中国剩余定理（EXCRT）