【裴蜀定理】
对于整数 $a,b$ 存在整数 $x,y$ 使得 $\text{gcd}(a,b)=ax+by$，
整数 $a,b$ 互质的充分必要条件是存在整数 $x,y$ 使得 $ax+by=1$。
证明：已知非零整数 $a,b$，记集合 $S=\{ax+by\mid x, y\in\mathbb{Z}\ \ \mathrm{and}\ \ ax+by>0\}$
记整数 $d=ax_0+by_0$ 为 $S$ 的最小元素。
我们只需要证明 $d=\text{gcd}(a,b)$ 就证明了裴蜀定理。
假设 $a=dq+r$ 其中 $q,r$ 是 $a$ 模 $d$ 的商和余数
$r=a-dq=a-(ax_0+by_0)q=a(1-x_0q)+b(y_0q)$
所以 $r \in S \cup \{0\}$，我们又知道 $0 \leq r < d$ 而 $d$ 又是 $S$ 的最小元素，所以 $r=0$。
这就意味着 $d \mid a$，同理可证明 $d \mid b$，又因为 $\text{gcd}(a,b) \mid d$，所以 $d=\text{gcd}(a,b)$。
另外，裴蜀等式的系数并不唯一，有无穷组系数 $(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}$ 是任意整数。