简介
上一篇文章简单介绍了欧几里得算法，即辗转相除法，它可以用于求解任意两个自然数 $a$ 和 $b$ 的最大公约数。而扩展欧几里得算法在求得 $gcd(a.b)$ 的同时，也能找到整数 $x$ 和 $y$ ,使它们满足裴蜀等式：
$$ax+by=gcd(a,b)$$
裴蜀定理
定义
在数论中，裴蜀定理是一个关于最大公约数的定理。
对任意两个整数 $a$、$b$，设 $g=gcd(a,b)$ 是它们的最大公约数。那么关于未知数 $x$ 和 $y$ 的线性裴蜀等式：
$$ax+by=m$$
有整数解 $(x, y)$ 当且仅当 $m$ 是 $g$ 的整数倍。
裴蜀等式有解时必然有无穷多个解，每组解 $(x,y)$ 都称为裴蜀数。
证明
维基百科中证明步骤的大概思路是这样的：
(1) 给出集合 $A = {ax+by|(x,y)\in\mathbb{Z}^2}$
(2) 通过$A\cap\mathbb{N}^*\neq\emptyset$，$\mathbb{N}$良序等讨论，指出$A$中必然存在最小正元素$d_0=ax_0+by_0$基本逻辑是这样的，中包含了$A$中所有的正元素，且$A\cap\mathbb{N}^*$是良序集合自然数集合$\mathbb{N}$的非空子集，故其中存在最小元素。也就是说集合$A$中存在最小正元素，记为$d_0$。
(3) 假设$p=ax+by$为$A$中任何一个正整数，试图计算$p$对$d_0$的带模除法，记为$p=qd_0+r$，因为$d_0$是$A$中最小正整数，故另一正整数$p$必然满足$p \geq d_0$，故$q > 0$，$0\leq r < d_0$
(4) 可得$r=p-qd_0=ax+by-q(ax_0+by_0)=a(x-qx_0)+b(y-qy_0)$，根据其形式可判断$r\in A$，结合上一条的结论$0\leq r < d_0$，且$d_0$是$A$中的最小正元素，可推断$r=0$，则可知$A$中任意正整数$p$都满足$p=qd_0$，即$A$中任意正整数$p$都是$d_0$的整数倍，记为$d_0|p$，并且显然$a \in A,b \in A$，故$d_0|a$，$d_0|b$，于是可知$d_0$是$a$和$b$的公约数只能判断是公约数，结合后面的证明才得出最大公约数的结论，并且，上面的论述没有仔细考虑$a$，$b$为负值的情况，裴蜀定理 - 维基百科的证明也许适用于负数
(5) 设$a$与$b$的任意公约数为$d$，则$a$与$b$可表示为$a=kd$，$b=ld$，那么$d_0=ax_0+by_0=kdx_0+ldy_0=(kx_0+ly_0)d$，可知$d|d_0$，也就是说$d_0$是任何$a$和$b$的公约数$d$的倍数，最大公约数也不例外，且由上一点可知$d_0$是$a$和$b$的公约数，由此可推断$d_0$本身就是$a$与$b$的最大公约数
(6) 关于解的数量无限的讨论，详见裴蜀定理 - 维基百科
(7) 总之，从上面的讨论可以得出如下结论：在集合$A = {ax+by|(x,y)\in\mathbb{Z}^2}$当中，最小正元素$d_0=gcd(a,b)$，且$A$中任意正元素都是$d_0$的倍数
(8) 因此如果$ax+by=m$有整数解，显然$m \in A$，根据上面的讨论可知 $gcd(a,b)|m$，即$m$是$gcd(a,b)$的整数倍
算法步骤
相比欧几里得算法，扩展欧几里得算法在计算余数($q_i$)和商($r_i$)的基础上又增加了两列数据：$s_i$和$t_i$，最终得到的$s_i$和$t_i$满足裴蜀等式：
$$as_i+bt_i=r_i=gcd(a,b)$$
具体算法步骤如下:
| 序号 | 余数$r_i$ | $s_i$ | $t_i$ |
|---|---|---|---|
| $0$ | $a$ | $1$ | $0$ |
| $1$ | $b$ | $0$ | $1$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $i+1$ | $r{i+1}=r{i-1}-q_ir_i$ | $s{i+1}=s{i-1}-q_is_i$ | $t{i+1}=t{i-1}-q_it_i$ |
终止条件与欧几里得算法相同，当$r_{i+1}=0$时终止，此时：
$$as_i+bt_i=r_i=gcd(a,b)$$
证明
上一篇文章证明了欧几里得算法的正确性，在此基础上说明扩展欧几里得算法的正确性。
当$i=0$时，$r_0=a,s_0=1,t_i=0$，显然满足$as_i+bt_i=r_i$
当$i=1$时，$r_1=b,s_0=0,t_i=1$，显然满足$as_i+bt_i=r_i$
由下列递推式可推及所有$i>1$时的情况：
$$\begin{equation}\begin{split}
r_{i+1}&=r_{i-1}-q_ir_i\\\\
&=(as_{i-1}+bt_{i-1})-q_i(as_i+bt_i)\\\\
&=a(s_{i-1}-q_is_i)-b(t_{i-1}-q_it_i)\\\\
&=as_{i+1}+bt_{i+1}
\end{split}\end{equation}$$
因此当$r_{i+1}=0$，算法终止时：
$$as_i+bt_i=r_i=gcd(a,b)$$
参考资料
扩展欧几里得算法 - 维基百科
辗转相除法 - 维基百科
裴蜀定理 - 维基百科
丢番图方程 - 维基百科
二元关系 - 维基百科
偏序关系 - 维基百科
全序关系 - 维基百科
良序关系 - 维基百科