裴蜀定理，又称为贝祖定理，是数论中的一个基本定理。它描述了两个整数的最大公约数（GCD）与它们的线性组合之间的关系。具体来说，如果 \(a\) 和 \(b\) 是两个非零整数，那么存在整数 \(x\) 和 \(y\)，使得：

\[ ax + by = \gcd(a, b) \]

这个等式表明，任意两个整数的线性组合可以表示出它们的最大公约数。

证明

我们来证明裴蜀定理。假设 \(a\) 和 \(b\) 是两个正整数，并且 \(a > b\)。我们将使用辗转相除法来证明这个定理。

第一步：定义最大公约数

设 \(d = \gcd(a, b)\)，这意味着 \(d\) 是能够同时整除 \(a\) 和 \(b\) 的最大正整数。

第二步：辗转相除法

根据辗转相除法，我们可以写成以下形式：

\[ a = bq_1 + r_1 \]

其中 \(q_1\) 是商，\(r_1\) 是余数，并且 \(0 \leq r_1 < b\)。由于 \(d\) 整除 \(a\) 和 \(b\)，所以 \(d\) 也必须整除 \(r_1\)。因此，\(\gcd(a, b) = \gcd(b, r_1)\)。

接下来，我们继续应用辗转相除法：

\[ b = r_1q_2 + r_2 \]

其中 \(q_2\) 是商，\(r_2\) 是余数，并且 \(0 \leq r_2 < r_1\)。同样地，\(\gcd(b, r_1) = \gcd(r_1, r_2)\)。

重复这个过程，直到余数为零。最终，我们会得到：

\[ \gcd(a, b) = r_n \]

其中 \(r_n\) 是最后一个非零余数。

第三步：构造线性组合

通过观察辗转相除法的过程，我们可以逆向构造出 \(x\) 和 \(y\)，使得：

\[ ax + by = \gcd(a, b) \]

这可以通过逐步回代的方法完成。例如，在最后一步中，我们有：

\[ r_{n-2} = r_{n-1}q_n + r_n \]

将 \(r_n\) 表示为 \(r_{n-2}\) 和 \(r_{n-1}\) 的线性组合，然后继续回代，直到表达式包含 \(a\) 和 \(b\)。

结论

通过上述步骤，我们证明了裴蜀定理，即对于任意两个整数 \(a\) 和 \(b\)，存在整数 \(x\) 和 \(y\)，使得：

\[ ax + by = \gcd(a, b) \]

这个定理在数论中有广泛的应用，特别是在求解线性丢番图方程和模算术问题时非常有用。