$$扩展欧几里得$$
【前置芝士】
至于欧几里得的基础算法就是辗转相除法，用式子来表示也就是，
$forall a , b , b eq0, gcd(a,b) = gcd(b,a mod b) $,
对于此，也就不证明其正确性了。
【其代码实现】：
gcd(a, b)//更相减损术
a, b = max(a, b), min(a, b)
while a != b:
a, b = max(b, a-b), min(b, a-b)
return a
gcd(a, b) // 辗转相除法
a, b = max(a, b), min(a, b)
while a % b != 0:
a, b = b, a%b
return b
【(gcd(a,b)和lcm(a,b))】
刚刚提到了(gcd(a,v))，那么求解(gcd)也就可以用上方的辗转相除法了。
那么(lcm(a,b))呢，$lcm(a,b) = a / gcd(a,b) imes b $
证明如下：
令 (x = gcd(a,b)).
则显然 (x mid a),(xmid b).
令 (a_0 = [a / x] , b_0 = [b / x]).
则 (lcm(a_0 , b_0) = a_0 imes b_0). (gcd(a_0,b_0) = 1)
(lcm(a_0,b_0) imes gcd(a_0,b_0) imes x = a_0 imes b_0 imes x)
又因为 ，最大公约数
所以 ， (lcm(a,b)= frac {a imes b}{x})
也就是 (lcm(a,b) imes x = a imes b)
所以 ， (lcm(a,b) imes gcd(a,b) = a imes b)
证毕，$over ~ $
【同余的性质】
1.(left ( a+b
ight )mod p=left (amod p+ bmod p
ight )mod p)
2.(left ( a-b
ight )mod p=left (amod p- bmod p
ight )mod p)
3.(left ( a imes b
ight )mod p=left (amod p) imes (bmod p
ight )mod p)
4.若(aequiv b(mod p))，那么(a^{n}equiv b^{n}(mod p))
5.若(amod p1=x，amod p2=x)，且(p1，p2)互质，(amod (p imes q)=x)
6.若(aequiv b(mod p))，(k)和(c)为整数，而且$k> 0 (，那么)a^{k}cequiv 7.b^{k}c(mod p)(
8.若)acequiv bc(mod p)(，那么)aequiv b(mod frac{p}{gcd(p,c)})(就可以推出)gcd(p,c)=1(，则有)aequiv b(mod p)$
【正篇】
【裴蜀定理】:
【前置芝士】
【定义】：
对于任意的整数(a,b)，关于未知数(x,y)的线性不定方程： 若(a,b)为整数，且(gcd=d)，那么对于任意的整数(x,y，) (d|(ax+by))
【推论】：
(a,b)互质的充分必要条件是存在整数(x,y)使(ax+by=1)
【证明1】：
设(d=gcd(a,b))则(d|a,d|b)由整除的性质,对于任意的整数(x,y)有(d|(ax+by))。
设(s)为(ax+by)最小正值。令(q=[frac{a}{s}])
则(r=amods=a-q(ax+by)=a(1-qy)+b(-qy))。
可见(r)也为(a,b)的线性组合。
由于(r)为(mods)所得,所以(0 leq r<s) 。
由于(s)为(a,b)线性组合的最小正值,可知(r=0)。
有(s|a),(s|b)，因此，s是a与b的公约数，所以(d>=s……)
因为(d|a,d|b),且(s)是(a,b)的一个线性组合，所以由整除性质知 (d|s)
但由于(d|s,s>0)，所以，(d<=s)
综上，(d=s)，证毕；
【证明2】
于下面中，可以通过目录跳转
【推广】：
方程 (ax+by+cz+……nm=f)有解的充要条件就是 (f)是(gcd(a,b,c,……，n))的倍数
【证明】：
充分性证明：
设gcd（a，b）=d，于是设a=k1d,b=k2d，c=k3*d其中k1，k2互质
那么原等式等价于k1dx+k2dy=k3d，即k1x+k2*y=k3，其中k1，k2互质
那么这个方程等价于模线性方程egin{matrix} k1*x & equiv & k3 &mod & k2 end{matrix}，由拓展gcd知，该方程一定有解
那么该方程的一组解即为原方程的解
必要性证明：
采用反证法，假设c不是gcd（a，b）的倍数，于是：
设a=k1d,b=k2d,c=k3*d+c{}'
那么：
k1dx+k2dy=k3*d+c{}'
两边同时除以d，有：
k1x+k2y=k3+frac{c{}'}{d}
由于k1,x,k2,y,k3均为整数，而frac{c{}'}{d}显然不是整数，故原方程无解
这与方程有解矛盾，故c一定为gcd(a,b)的倍数
例题：裴蜀定理
code:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
int n;
int main()
{
scanf("%d", &n);
int ans = 0,s;
for(int i=1; i<=n; i++)
{
scanf("%d", &s);
s=abs(s);
ans = gcd(ans, s);
}
printf("%d", ans);
}
【扩展欧几里得】:
【杂言】：
一般是用来求解线性不定方程，同余方程和逆元的
【引理】：
存在 (x , y) 使得 (gcd(a,b)=a imes x+b imes y)（bezout定理）
————来源于李煜东《算法竞赛进阶指南》
【证明】：
在欧几里得的算法的最后一步，即(b=0)时，显然有一对整数(x=1, , y = 0),
使得(a imes b + 0 imes 0 = gcd(a,0))
若(b > 0)时，则(gcd(a,b)=gcd(b,a mod b))。
假设存在一对整数(x,y)，满足(b imes x + (a mod b ) imes y = gcd(b,a mod b)),
因为(b imes x + (a - b imes [a/b]) imes y = a imes y + b imes(x - [a/b] imes y)),
所以令 (x^{'}=y,y^{'} = x -[a/b] imes y),
也就得到了(a imes x^{'} + b imes y^{'}=gcd(a,b))
对欧几里得算法的递归过程进行数学归纳法，得证
证毕
上文的证明，就是按照欧几里得的思路来证明的，且同时给出了如何求解(x,y)，这种的计算方法叫做 扩展欧几里得
同余方程，即和上方一致，上方已经给出了其求解(x,y)的值的方法了。