引言
再看扩展欧几里得的时候，我一直有一个疑问，即：
为什么扩欧一定有解？
我们可以通过说明欧几里得算法一定有解，来论证扩展欧几里得也一定有解。这显然是正确的，但是这个结论总感觉有点微妙。
我们不妨来考虑下面这个问题：对于方程
$$
ax+by=m, a,b,m\in\mathbb Z
$$
有整数解 $(a,b)$ 的充要条件是什么？
在这里，我们引入裴蜀定理。
裴蜀定理
对于任意两个整数 $a,b$，设 $d = \gcd(a,b)$。那么关于未知数 $x,y$ 的线性方程（裴蜀等式）：
$$
ax+by=m
$$
有整数解 $(x,y)$ 当且仅当 $m$ 为 $d$ 的整数倍。
裴蜀等式有解时必然有无穷多个解。
证明
讨论：
(1) 若 $a,b$ 中有一个为 $0$，不失一般性，设 $a=0$，那么他们的最大公约数 $d=b$，裴蜀等式也变为：
$$
by=m
$$
当且仅当 $m$ 为 $b$ (即 $d$) 的倍数时，方程有解。由于 $x$ 可以为任意整数，所以有解时裴蜀等式必然有无穷多组解。证毕。
(2) 若 $ab \neq 0$
考察集合
$$
A=\{xa+yb|(x,y)\in\mathbb Z^2\}
$$
下面证明 $A$ 中的最小正元素等于 $\gcd(a,b)$。
首先，$A\cap \mathbb N^*$ 不是空集，因为至少有 $|a|,|b|\in A$。根据最小数存在定理，$A$ 中必然存在最小正元素，我们记作 $d_0 = x_0 a + y_0 b$。考虑 $A$ 中的任意一个元素 $p = x_1 a + y_1 b$ 对于 $d_0$ 的带余除法：设
$$
p = qd_0 + r, 0 \leq r < d_0
$$
由于
$$
r = p - qd_0 = (x_1 - qx_0) a + (y_1 - qy_0) b \in A
$$
因为 $0 \leq r < d_0$ 且 $d_0$ 为 $A$ 的最小正元素，我们可以得到 $r = 0$，即 $d_0 \mid p$。即，$A$ 中的任意元素 $p$ 都是 $d_0$ 的倍数。
特别地，我们取：
$$
\begin{cases}
x = \operatorname{sgn}(a) \\
y = 0
\end{cases}, \begin{cases}
x = 0 \\
y = \operatorname{sgn}(b)
\end{cases}
$$
可以得到：
$$
d_0 \mid a, d_0 \mid b
$$
故 $d_0$ 为 $a,b$ 的公约数。
接下来，我们证明 $d_0$ 为 $a,b$ 的最大公约数。
对于 $a,b$ 的任意正公约数 $d$，设 $a = kd, b=ld$，则
$$
d_0 = x_0 a + y_0 b = (x_0 k + y_0 l) d
$$
故 $d \mid d_0$，且必然有 $d_0\geq d$，故我们可以得出
$$
d_0 = \max d = \gcd(a,b)
$$
也就是说，我们证明了：$A$ 中的任意元素 $p$ 都是 $\gcd(a,b)$ 的倍数。即，方程 $ax+by=m$ 有整数解时，$m$ 必然为 $\gcd(a,b)$ 的倍数时。由此，我们证明了定理的充分性。
必要性证明：
我们已经证明了
$$
ax+by=\gcd(a,b)=d_0
$$
时方程有解，解记作 $(x_0,y_0)$。对于 $d_0$ 的任意倍数 $t$，此裴蜀等式的解即为 $(tx_0,ty_0)$。必然有解。
此外，我们再给出裴蜀等式无穷多组解的解集：
对于裴蜀等式：
$$
ax+by=m_0d_0, d_0=\gcd(a,b)
$$
有
$$
(x,y)\in\Big\{\Big(mx_0 + \frac {kb} d,my_0 - \frac {ka} d\Big)\Big|k\in\mathbb Z\Big\}
$$
特例
注意：裴蜀定理有非常有用的特例：
方程 $ax+by=1$ 有整数解 $(x,y)$ 当且仅当 $a,b$ 互素，即 $\gcd(a,b)=1, a\perp b$。
