贝祖定理(Bézout’s theorem,Bézout’s Identity) 是数论中一个关于最大公约数的定理,它说明了对于任意两个整数 ,存在整数 ,使得 等于它们的最大公约数的倍数。 互质,当且仅当存在两个整数 ,使得 等于 1。

贝祖定理的证明可以使用辗转相除法(欧几里得算法)来进行。证明分为两种情况:

  1. 中存在一个数为零时,不妨设 为零。此时,有 的任意整数倍都可以被 整除,因此对于任意整数 ,都有 。所以贝祖定理成立。
  2. 中的数都不为零时,使用辗转相除法进行证明:
    • 首先,根据辗转相除法,我们可以得到 的最大公约数 ,以及一组整数 ,使得 ,其中
    • 假设存在整数 ,使得 。我们可以将 替换为 ,得到
    • 将上式进行变形,得到 。由于 ,所以 仍然等于 的倍数。
    • 因此,我们可以将 替换为 ,得到 。继续进行变形,得到
    • 通过不断进行变形,我们可以得到一系列的等式,最终得到 ,其中 为整数。
    • 由于 ,所以 仍然等于 的倍数。
    • 因此,我们可以得到一组整数 ,使得

综上所述,贝祖定理成立。


例子: 有两个数 3 和 7,找到 的整数解。

既然 3 和 7 是互素的,我们可以通过扩展欧几里得算法找到满足 的整数解。

我们可以从 7 除以 3 开始:

这里我们已经找到了余数 1,这就是我们想要的,因为这表示 1 可以表示为 3 和 7 的线性组合。现在我们可以回溯以找到对应的 x 和 y 值。

从上面的等式我们可以直接得到:

在这个等式中,我们可以看到:

所以, 的一个整数解是 。这不是唯一的解,因为我们可以通过以下方式获得无限多个解:

这里 k 可以是任意整数。每一个不同的 k 值都会给我们一个新的解。原因是如果 是方程的一个解,那么 也是一个解,因为:

这就保证了加上这些倍数不会改变等式的值。


例子:有两个数 3 和 7 互素,请找到 的整数解。

我们要找到方程 的整数解。这个方程是一个线性丢番图方程,可以通过扩展欧几里得算法(Extended Euclidean Algorithm)来找到整数解。

扩展欧几里得算法不仅能计算出两个整数的最大公约数,还能找到满足以下等式的整数

在我们的例子中,,且 ,因为 3 和 5 是互素的。

下面是使用扩展欧几里得算法求解 的步骤:

  1. 由于 ,我们先计算 除以 的商和余数:

  2. 然后,用 除以上一步得到的余数

  3. 接着用 除以上一步得到的余数

    一旦余数为 ,我们就可以停止计算。最后一个非零余数 就是 的最大公约数。

现在我们开始回代找到

  1. 开始,我们看到:

  2. 替换步骤 1 中的

现在我们得到了 的值:

所以, 的一个整数解是