请证明裴蜀定理
裴蜀定理（Bézout’s Lemma）是数论中的一个基本定理。它陈述了两个整数的最大公约数可以表示为这两个整数的线性组合。
Bézout’s Lemma
对于任意两个整数 $a$ 和 $b$，设 $d = \gcd(a, b)$，则存在整数 $x$ 和 $y$，使得：
$ ax + by = d $
证明
我们通过欧几里得算法来证明这一点。
步骤 1：定义 $\gcd(a, b)$
设 $d = \gcd(a, b)$。根据最大公约数的定义，$d$ 是 $a$ 和 $b$ 的公约数，且任何其他的公约数都是 $d$ 的约数。
步骤 2：欧几里得算法
欧几里得算法提供了一种计算两个数的最大公约数的方法。我们通过一系列的除法步骤来计算。
假设 $a$ 和 $b$ 是非负整数且 $a \ge b$，我们进行以下步骤：
$ a = bq_1 + r_1 $
$ b = r_1q_2 + r_2 $
$ r_1 = r_2q_3 + r_3 $
$ \ldots $
直到某个余数 $r_k = 0$，此时，$d = r_{k-1}$。
作者注：若 $a = bq + r$，则 $gcd(a, b) = gcd(b, r)$。
通过这些步骤，我们得到：
$ d = r_{k-1} $
作者注：最后一个公式 $r_{k - 2} = r_{k - 1}q_k + 0$。
步骤 3：倒推求解
从欧几里得算法的最后一步开始倒推，我们可以将每个余数表示为 $a$ 和 $b$ 的线性组合。
- 最后一非零余数 $r_{k-1}$ 可以表示为：
$ r_{k-1} = r_{k-2} - r_{k-3}q_k $
作者注：上述公式有误
- 再往前一步，$r_{k-2}$ 和 $r_{k-3}$ 都可以表示为之前余数的组合：
$ r_{k-2} = r_{k-3} - r_{k-4}q_{k-1} $
$ r_{k-3} = r_{k-4} - r_{k-5}q_{k-2} $
作者注：上述公式有误
继续这个过程，我们最终可以将 $r_{k-1}$ 表示为 $a$ 和 $b$ 的线性组合。
步骤 4：线性组合
通过反复替代每一步中的余数，最终我们可以得到：
$ d = r_{k-1} = ax + by $
其中，$x$ 和 $y$ 是整数。
作者注：结论正确，倒推公式不正确。应改为：
$d = r_{k - 1}$
$r_{k - 3} = r_{k - 2}q_{k - 1} + r_{k - 1} \rightarrow d = r_{k - 3} - r_{k - 2}q_{k - 1} = r_{k - 3}x_0 + r_{k - 2}y_0$
$ \begin{aligned} r_{k - 4} = r_{k - 3}q_{k - 2} + r_{k - 2} \rightarrow d &= r_{k - 3} - (r_{k - 4} - r_{k - 3}q_{k - 2})q_{k - 1} \\ &= r_{k-4}(-q_{k - 1}) + r_{k-3}(1 + q_{k-2}q_{k-1}) \\ &= r_{k - 4}x_1 + r_{k - 3}y_1 \end{aligned} $
…
$r_1 = r_2q_3 + r_3 \rightarrow d = r_1x_{k - 4} + r_2y_{k - 4}$
$b = r_1q_2 + r_2 \rightarrow d = bx_{k - 3} + r_1y_{k - 3}$
$a = bq_1 + r_1 \rightarrow d = ax_{k - 2} + by_{k - 2}$
满足 $x_{i+1} = y_{i}, y_{i+1} = x_{i} - q_{k-2-i}y_{i}$
结论
我们已经通过欧几里得算法的步骤和倒推过程证明了裴蜀定理：对于任意整数 $a$ 和 $b$，其最大公约数 $d$ 可以表示为 $a$ 和 $b$ 的线性组合。即存在整数 $x$ 和 $y$，使得：
$ ax + by = d $
这就是裴蜀定理的完整证明。
如何证明 $d$ 是最小的 $ax + by$
为了证明 $\gcd(a, b)$ 是可以表示为 $ax + by$ 的最小正整数，我们将采用如下证明方法：
定理陈述
设 $a$ 和 $b$ 是两个整数，且 $d = \gcd(a, b)$。我们要证明 $d$ 是可以表示为 $ax + by$ 的最小正整数。
证明
步骤 1：存在性
根据裴蜀定理（Bézout’s Lemma），我们知道存在整数 $x$ 和 $y$，使得：
$ ax + by = d $
其中 $d = \gcd(a, b)$。
步骤 2：最小正整数
现在，我们要证明 $d$ 是可以表示为 $ax + by$ 的最小正整数。为此，我们设 $S$ 是所有可以表示为 $ax + by$ 的正整数集合：
$ S = \{ax + by \mid x, y \in \mathbb{Z} \text{且} \ ax + by > 0 \} $
我们需要证明 $d$ 是集合 $S$ 中的最小元素。
步骤 3：设 $m$ 为 $S$ 中的最小正整数
设 $m$ 是 $S$ 中的最小正整数，即：
$ m = ax_0 + by_0 $
其中 $x_0$ 和 $y_0$ 是某些整数。
我们需要证明 $m = d$。
步骤 4：$m$ 的性质
因为 $m \in S$，所以 $m$ 可以表示为 $ax + by$ 的形式。我们还知道，$d$ 是 $a$ 和 $b$ 的最大公约数。我们现在要证明 $d$ 是 $m$ 的约数。
假设 $a = q_1m + r_1$，其中 $0 \le r_1 < m$。根据除法定理，$q_1$ 和 $r_1$ 是整数。
作者注：由于 $m$ 是最小的 $ax + by$，因此 $m \le a \times 1 + b \times 0$，即 $m \le a$。
步骤 5：检查余数 $r_1$
我们有：
$ r_1 = a - q_1m $
由于 $m$ 是 $ax + by$ 的形式，我们可以写成：
$ r_1 = a - q_1(ax_0 + by_0) = a(1 - q_1x_0) + b(-q_1y_0) $
因此，$r_1$ 也可以表示为 $a$ 和 $b$ 的线性组合。所以如果 $r_1 > 0$，则 $r_1 \in S$，这与 $m$ 是 $S$ 中的最小正整数矛盾。因此，$r_1$ 必须为 0。
所以：
$ r_1 = 0 \Rightarrow a = q_1m $
这意味着 $m$ 整除 $a$。
步骤 6：对 $b$ 的同样处理
类似地，我们可以写：
$ b = q_2m + r_2 $
其中 $0 \le r_2 < m$。
再根据同样的逻辑：
$ r_2 = b - q_2m = b - q_2(ax_0 + by_0) = a(-q_2x_0) + b(1 - q_2y_0) $
所以 $r_2$ 也可以表示为 $a$ 和 $b$ 的线性组合。如果 $r_2 > 0$，则 $r_2 \in S$，这与 $m$ 是 $S$ 中的最小正整数矛盾。因此，$r_2$ 必须为 0。
所以：
$ r_2 = 0 \Rightarrow b = q_2m $
这意味着 $m$ 也整除 $b$。
步骤 7：$m = d$
由于 $m$ 是同时整除 $a$ 和 $b$ 的正整数，所以它至少是它们的最大公约数 $d$ 的倍数。因为 $d$ 是最大公约数，所以它是所有整除 $a$ 和 $b$ 的数中最大的。因此，$m$ 必须等于 $d$。
作者注：上面的浅色段落出现逻辑错误，应修正为：
- $m \mid a, m \mid b \rightarrow m \mid d \rightarrow m \le d$。
- $d \mid a, d \mid b \rightarrow d \mid m \rightarrow d \le m$。
因此，$m = d$。
结论
我们已经证明了 $d = \gcd(a, b)$ 是可以表示为 $ax + by$ 的最小正整数。这就是裴蜀定理的完整证明。
我的补充
证明 $d$ 是最小的 $ax + by$ 可以更简单：假设 $m = ax + by < d$，由于 $d \mid a, d \mid b$，因此 $d \mid m$，因此 $d \le m$，这与 $d > m$ 矛盾。
