学习笔记：证明裴蜀定理

如果有 $d = \gcd(a,b)$，则一定有 $d \mid (ax + by)$，且 $ax + by = k \times \gcd(a,b)$。

对于任意 $(a,b)$，有最小的 $(x,y)$ 使得 $ax + by = \gcd(a,b)$

集合

设 $d = ax_0 + by_0$ 为集合中最小正值。

我们需要证明 $d = \gcd(a,b)$。

首先要证明 $d \mid a$ 且 $d \mid b$。

对于整数除法 $a \div b$，使得存在商 $q$，余数 $r (0 \le r < d)$，有：

将 $d = ax_0 + by_0$ 代入，得：

注意到 $r$ 竟然也是 $ax + by$ 的形式。

由于 $0 \le r < d$，$d$ 为集合最小正值且 $d > 0$，那么 $r$ 只能为 $0$。

那么 $a = qd$，即 $d \mid a$。

同理可证，$d \mid b$。

我们已经证明 $d$ 为 $a,b$ 公约数，接下来需要证明 $d$ 为 $a,b$ 的最大公约数。

设 $c = \gcd(a,b)$，则有 $c \mid a$ 和 $c \mid b$。

又因为 $a = c \times m,b = c \times n$，那么：

当 $x$ 取 $x_0$ 值，$y$ 取 $y_0$ 值时：

由于 $c = \gcd(a.b)$ 且 $d \mid a,d \mid b$，那么 $c \ge d$。

又因为 $c \mid d$，那么 $c \le d$。

由此得出 $c = d$，即：

证毕。