【裴蜀定理】
裴蜀定理，又称贝祖定理（Bézout's lemma）。是一个关于最大公约数的定理。
设 $a,\ b$ 是不全为零的整数，则存在整数 $x,\ y$, 使得 $ax+by=\text{gcd}(a,\ b)$。
也就是有解的充要条件是 $gcd(a,b)|c$。
【证明】
1. 若任何一个等于 $0$，我们假设 $b=0$。则 $\text{gcd}(a,\ b)=a$，这时定理显然成立。
2. 若 $a \neq 0,\ b \neq 0$。由于 $\text{gcd}(a,\ b)=\text{gcd}(a,\ -b)$。
不妨假设 $a \geq b>0,\ \text{gcd}(a,\ b)=d$。
对 $ax+by=d$ 两遍除以 $d$，可得 $a_1x+b_1y=1$，其中 $(a_1,\ b_1)=1$。
那么问题就变成证明 $a_1x+b_1y=1$。
我们先回顾一下辗转相除法是怎么做的，由 $\text{gcd}(a,\ b) \rightarrow \text{gcd}(b,\ a\ \text{mod}\ b) \rightarrow \cdots$，我们把模出来的数据叫做 $r$ 于是，有
$\text{gcd}(a_1,\ b_1)  = \text{gcd}(b_1,\ r_1) = \text{gcd}(r_1,\ r_1) = \cdots = \text{gcd}(r_{n-1},\ r_n)=1$
把辗转相除法中的运算展开，做成带余数的除法，得
$ \begin{matrix}
a_1=q_1b+r_1 & & (0 \leq r_1 < b_1)\\\\
b_2=q_2r_1+r_2 & & (0 \leq r_2 < r_1)\\\\
r_1=q_3r_2+r_3 & & (0 \leq r_3 < r_2) \\\\
\dots & &\\\\
r_{n-3}=q_{n-1}r_{n-2}+r_{n-1} & & (0 \leq r_{n-3} < r_{n-1})\\\\
r_{n-2}=q_{n}r_{n-1}+r_{n} & & (0 \leq r_{n-1} < r_{n})\\\\
r_{n-1}=q_{n+1}r_{n} & &
\end{matrix} $
不妨令辗转相除法在除到互质的时候退出则 $r_n=1$ 所以有（$q$ 被换成了 $x$，为了符合最终形式）
$r_{n-2}=x_{n}r_{n-1}+1$
即
$1=r_{n-2}-x_{n}r_{n-1}$
由倒数第三个式子 $r_{n-3}=q_{n-1}r_{n-2}+r_{n-1}$ 代入上式，得
$1=(1+x_{n}x_{n-1})r_{n-2}-x_{n}r_{n-3}$
然后用同样的办法用它上面的等式逐个地消去 $r_{n-2},\ \dots,\ r_{1}$，
可证得 $1=a_1x+b_1y$ 这样等于是一般式中 $d=1$ 的情况。

裴蜀等式的系数并不唯一，有无穷组系数 $(x,y)$ 能满足 $\text{gcd}(a,b)=ax+by$，
事实上，如果 $(x,y)$ 是一组系数，那么所有系数可以表示为
$\left(x+k\cdot\frac{b}{\gcd(a, b)} ,\ y-k\cdot\frac{a}{\gcd(a, b)}\right)$
其中 $k\in\mathbb{Z}$ 是任意整数。


【OI考点】
对于 $\forall\ x,y \in \mathbb{Z}$
函数 $f(x,y)=ax+by$ 的最小正整数取值为 $f(x,y)=gcd(a,b)$。