扩展欧几里得定理-扩展欧几里得定理

想象一下，你手里有一串数字，比如 234 和 156，你想算出它们最大公约数是多少。
一般的做法是把大数拆分成小数，不断用减法要么除法，直到最终拿到那个再也分不掉的数。
这听起来挺像做加法题，但要是数字特别大，手算起来就得累死，就连还会卡壳。
这时候欧几里得定理就登场了，它是古希腊数学家欧几里得当年用来取公因子的方式，后来演变成计算机处理数论的各种神器。 这方式的核心实际上就一句话：两个数的最大公约数，等于其中较小的数，跟它们余数最大的那个数的最大公约数。举个最好办的例子，60 和 156。先算 156 除以 60，商是 2，余数是 36。
那目前咱们就得找 60 和 36 的最大公约数了。60 除以 36，商是 1，余数是 24。
接着换一组找，36 除以 24，商 1，余数变成 12。
最终，24 除以 12，正好整除，商是 2，余数是 0。
这时候余数没了，剩下的 12 就是最大公约数。整个过程跑完了，比手算快多了。 不过，要是直接如此算，数据大的时候确实血泪横。假设我们要算两个数，它们的阶乘乘除起来简直是个庞大的迷宫，每一个步骤都要像迷宫一样反复计算，效率低到离谱。
这时候就需求一个更优雅的算法，也就是扩展欧几里得定理。
这个定理不光告诉你结局，还能顺便算出达到这个结局的“系数”，也就是说，它能让你反向找到两个原始数是如何一步步凑出来的。 在小数阶段，它是绝对的神。
比如我们要算 351 和 243 的最大公约数。直接除，351 除以 243，商是 1，余数是 108。再算，243 除以 108，商是 2，余数 27。最终 108 除以 27，商正好是 4，余数为 0。最大公约数就是 27。但咱们还得把系数一并求出来。从 351 到 243 除以 108 再除以 27，总共有四个步骤，每一步的商加起来——1 + 2 + 4 = 7。
也就是说，351 乘以 7 等于 243 的 4 倍。
这实际上就是著名的恒等式：351 × 7 - 243 × 7 = 27。
这个恒等式在小数里贼有用，但一旦涉及大数，这种逐个累加商的方式效率就低得让人发指。 为了优化这个过程，我们就引入了“带余除法组”。在每一步除法里，我们不仅记录余数，还顺便记下来商，然后把这两个数构建成一组。比方说刚刚的例子，我们就把 (243, 108, 商 2) 视为第一组数据，把 (108, 27, 商 4) 视为第二组。
这时候，我们的任务就变成了在两组数据里，找出一个数，能让另一组里的两个数通过它变成余数。我们设这个数为 x。把第二组的数据代入第一组，拿到 243 x - 108 (x 的某个组合) = 余数。我们不断把这一组的数据替换成新的数据，直到只剩下一组数为止。当数组只剩下一个数的时候，这最终一个数就是我们要找的 x。 在实际计算中，我们能够用递归的方式来做。假设我们要解方程 g(a, b, k)，其中 g 表示求最大公约数，k 是用来凑齐余数的系数。递归的思想就是：要是 b 能被 a 整除，那么 k 就等于 b 除以 a 的商；否则，k 就等于“k 乘以商”加上“a 除以 b 的商”。
这种递归写起来别看有点啰嗦，但逻辑贼清楚，没有那么多复杂的循环嵌套，读起来也撇脱。 举个例子，算 351 和 243 的最大公约数。初始状态是两数，系数为 1。
第一次递归调用 351 和 243。出于 243 不能整除 351，故此我们要把 351 除以 243 的商（1）乘进去，加上 243 除以 351 的商（0，要么说 0 的倒数在整数域里不忒好定义，这里简化处理，实际上是按照余数链来）。
实际上更直观的理解是，我们构建一个方程：351 × c1 - 243 × c0 = r。
第一次调用时，c1 初始为 1，c0 初始为 0。当执行 351 = 243 × 1 + 108，这一层里，c1 就要加上 1，c0 也要乘以 1。
接着 243 = 108 × 2 + 27，这一层 c1 加上 2，c0 加上 2。最终 108 = 27 × 4 + 0，这里 c1 加上 4，c0 加上 4。我们一直往前回溯，把每一层的商加起来。初始的 c1 是 1，第一次递归加 1，第二次加 2，第三次加 4，总共是 7。
这跟我们之前手算恒等式里的 7 一模一样。 要是你只是单纯想要最大公约数，实际上不需求如此折腾系数。但要是你想知道这两个数是如何通过线性组合拿到最大公约数的，要么想知道它们之间到底有多大倍数关系，扩展欧几里得定理就派上用场了。它的实现一般是通过两个变量来跟踪中间结局，一个存余数，一个存系数。
每次递归时，新的余数替换旧的余数，新的系数是旧的系数乘以商再加上旧的系数。
这样不需求重新计算，效率极高。 自然，代码实现的时候要注意细节。
比如初始值要设对，递归的 base case 如何处理，还有递归深度会不会溢出，这些都是实际开发中需求踩的坑。大局部现代语言要么编译器都有内置的函数，比如 C++ 里的 `gcd` 要么 `gcd`，它们本质上就是这段递归逻辑的封装。用它们的优点是不输自己手写，还能避免大量边界情况。 总而言之，扩展欧几里得定理把古老的数论精华又提升到了一个更高的维度。它不光解决了“求最大公约数”这个难题，更供给了一种从因数分解走向原数的逆向路径，是寻找最大公因子的终极工具。