贝祖定理 | 亚图跨际

贝祖定理是数论中的一个基本结果，它描述了两个整数的最大公约数（GCD）的一个特殊性质。它指出，两个整数的最大公约数总是可以表示为这两个整数的线性组合。

让我们分解一下这个定理：

gcd(a, b): 这表示两个整数 a 和 b 的最大公约数。GCD 是能同时整除 a 和 b 的最大正整数，且没有余数。
r * a + s * b = g: 这是贝祖定理的核心。它指出，存在整数 r 和 s，使得当你将 r 乘以 a，s 乘以 b，然后将结果相加时，你会得到 a 和 b 的 GCD (g)。整数 r 和 s 通常被称为贝祖系数。

为什么这很重要？

贝祖定理是一个强大的工具，在数学和计算机科学的各个领域都有应用，包括：

例子：

让我们取 a = 12 和 b = 18。12 和 18 的 GCD 是 6。贝祖定理告诉我们，我们可以找到整数 r 和 s，使得 12r + 18s = 6。在这种情况下，我们可以选择 r = -1 和 s = 1，因为 (-1)*12 + (1)*18 = 6。

主要收获： 贝祖定理保证了存在满足线性组合方程的整数 r 和 s，将两个数的 GCD 连接到这两个数的特定线性组合。

解释和输出：

extended_gcd(a, b) 函数： 此函数实现扩展欧几里得算法。它递归地计算 GCD 以及系数 r 和 s。基本情况是当 a 为 0 时，在这种情况下，GCD 是 b，系数是 r=0 和 s=1。递归步骤使用模运算符 (%) 将问题简化为更小的输入。
演示： 然后，代码通过几个示例演示了该函数的使用。它打印出每对数字的 GCD 以及系数 r 和 s。它还验证了等式 ra + sb = g 是否成立。

示例输出：

此输出表明，对于每对整数 a 和 b，代码成功找到满足贝祖恒等式的 GCD 和贝祖系数 r 和 s。这提供了贝祖定理的实际演示。