其实挺简单。
GCD（辗转相除法）
定理：
\[\gcd(a , b) = \gcd(b , a \% b) \]证明：
\[\text{设 } a = kb + r \text{ ，则 } r = a \bmod b \]\[\text{若 } c \text{ 是 } a,b \text{ 的一个公约数，则 } c \mid a,c \mid b \]\[\because r = a - kb \]\[\therefore c \mid r \]\[\therefore c \text{ 是 } b,a \bmod b \text{ 的公约数} \]\[\text{同理，若 } d \text{ 是 } b,a \bmod b \text{ 的公约数，则 } d \mid b,d \mid r \]\[\because a = kb + r \]\[\therefore d \mid a \]\[\therefore d \text{ 也是 } a,b \text{ 的公约数} \]\[\therefore a,b \text{ 和 } b,a \bmod b \text{ 的公约数是一样的，其最大公约数也必然相等，证毕} \]code（递归式）:
int gcd(int a,int b){
return (b==0)?a:gcd(b,a%b);
}
EXGCD（扩展欧几里得）
裴蜀定理：
\[\forall a,b \in Z \text{ , } \exists x,y \in Z \]满足
\[ax+by=\gcd(x,y) \]证明（类似递归）：
当 b=0 时:
\[\gcd(a,b)=a \text{ ，此时 } x=1 , y=0 \]当 b!=0 时：
\[\text{设 } ax1+by1=gcd(a,b)=gcd(b,a%b)=bx2+(a%b)y2 \]\[\because a \bmod b = a - a / b * b \]\[\therefore ax1 + by1 = bx 2+ (a - a / b * b) y2 \]\[\therefore ax1 + by1 = bx2 + ay2 - a / b * by2 \]\[\therefore ax1 + by1 = ay2 + bx2 - b * a/b * y2 \]\[\therefore ax1 + by1 = ay2 + b (x2 - a / b * y2) \]\[\text{解得 } x1 = y2 , y1 = x2 - a / b * y2 \]用类似递归的方法即可得证。
通过这个证明，我们发现可以在维护 \(\gcd\) 时同时维护 \(x,y\) 的值。
code:
int exgcd(int a,int b,int &x,int &y){
if(b==0) {x=1,y=0;return a;}
else{
int ans=exgcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
}
用途（1，2为基本用途）：
1.
首先看怎么解
\[ax+by=c \]这类方程
首先：若 \(\gcd(a,b) \nmid c\) 可以知道原方程没有整数解（等式左右因数不相等，显然无整数解。
所以我们将原方程左边 \(\times \gcd(a,b) / c\) ,然后通过解 \(ax_0+by_0=\gcd(a,b)\) 解得 \(x_0,y_0\) ，最后将 \(x_0,y_0\) 乘上 \(c / \gcd(a,b)\) 解出原方程的一组解 \(x_1,y_1\).
显然，我们将 \(x_1 + b / \gcd(a,b) * t,y_1 - a/ \gcd(a,b) * t\) （ \(t\) 为任意整数）即可得出所有解。
2.
然后，我们再来看下同余方程
\[ax\equiv l \pmod{m} \]其实稍加转化，就得到了
\[ax+my=l \]解这个方程即可，注意 \(x\) 的特殊要求。
3.
最后，我们来看一下同余方程组
\[\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} \]若所有 \(m\) 互质，可以用 \(crt\) 求解。
这里主要说不互质的用 \(exgcd\) 解法
首先看第一二个式子：
变形得到：
\[\begin{cases} x = a_1 + m_1k_1 \\ x = a_2 + m_2k_2\end{cases} \]\[\therefore a_1+m_1k_1=a_2+m_2k_2 \]整理：
\[m_1k_1-m_2k_2=a_2-a_1 \]运用 \(exgcd\) 解得 \(k_1\) 的一组解：
\[k_1=r \]\[\therefore k_1 \text{ 的通解为 } k_1=r+\frac{m_2}{\gcd(m_1,m_2)} \times t \mid t \in Z \]将上式带入 \(x = a_1 + m_1k_1\) 得：
\[x=a_1+m_1r+\frac{m_1m_2}{\gcd(m_1,m_2)}\times t \]\[\because \operatorname{lcm(m_1,m_2)}=\frac{m_1m_2}{\gcd(m_1,m_2)} \]\[\therefore x=a_1+m_1r+\operatorname{lcm(m_1,m_2)}\times t \]变形得到：
\[x\equiv a_1+m_1r\pmod{\operatorname{lcm(m_1,m_2)}} \]于是我们就成功将两个同余方程化简成了一个。
同理化简下去直到一个，求解即可。
例题
——后来 jijidawang 说这就是 \([excrt](https://www.cnblogs.com/xrlong/p/17073430.html)\)。
标签：gcd,int,text,欧几里得,Exgcd,pmod,算法,therefore,equiv From： https://www.cnblogs.com/xrlong/p/17069248.html