Python欧几里得算法计算最大公约数过程详解

首先明确一个核心观点：求解最大公约数（GCD）是小学数学中的经典问题，但当时多数人只记住了定义，并未掌握真正高效的算法。欧几里得算法（又称辗转相除法）正是处理这一问题的利器——它能快速计算出两个自然数的最大公约数，前提是这两个数不能同时为零。本文将带你一步步透彻理解这一算法。

从暴力枚举开始

我们先从最直接的暴力方法入手。按照定义硬算，思路非常简单：从较小的数开始逐一递减，直到找到能同时整除两个数的那个最大整数。逻辑上没有问题，但效率实在不敢恭维。

对应的Python代码如下：

def brute_force_gcd(a, b):
    if a == 0 and b == 0:
        raise ValueError("a and b cannot be both 0")
    if a == 0:
        return b
    if b == 0:
        return a
    candidate = min(a, b)
    while True:
        if a % candidate == 0 and b % candidate == 0:
            return candidate
        candidate -= 1

因为所有自然数都能被1整除，所以计算出的最大公约数至少为1，这一点没有问题。

寻找规律：固定一个数，观察结果

接下来，我们来做一件数学家经常做的事：寻找规律。固定其中一个数 b 不变，让 a 变化（反过来也一样，没有区别），看看最大公约数的结果是否存在某种模式。

b = 1 时

当 b=1 时，无论 a 取何值，gcd(a,1) 都等于1，显然成立。

b = 2 时

当 b=2 时，我们来列举几个 a 的值：

规律非常明显——结果要么是1，要么是2，交替出现。为什么呢？
当 a 是偶数时，2能整除 a 和 2，因此 gcd=2
当 a 是奇数时，2不能整除 a，最大公约数不可能等于2，所以 gcd=1

b = 3 时

同理，我们来看 b=3 的情况：

周期为3,1,1，反复循环。原因如下：
a ≡ 0 (mod 3) 时，3能同时整除 a 和 3，gcd=3
a ≡ 1 (mod 3) 时，3不能整除 a，2也不能整除3，因此 gcd=1
a ≡ 2 (mod 3) 时，同理可得 gcd=1

b = 4 时

再来看 b=4：

结果是4,1,2,1，周期为4。解释起来也不复杂：
a ≡ 0 (mod 4) → gcd=4
a ≡ 1 (mod 4) → 4不能整除a，3不能整除4，2不能整除a，只能等于1
a ≡ 2 (mod 4) → 4不能整除a，但2可以同时整除a和4，所以 gcd=2
a ≡ 3 (mod 4) → 全都不能整除，gcd=1

推广到一般情形

观察完这几个小例子后，我们尝试提炼出一个更通用的规律。假设 a ≥ b，下面这个等式似乎成立：

gcd(a, b) = gcd(a - b, b)

我们来尝试证明它。记 gcd(a,b)=g，gcd(a-b,b)=g'。

先从左边推导到右边：
因为 g|a 且 g|b，所以 g|(a-b)。g 既是 a-b 的约数，又是 b 的约数，那么它一定是 a-b 和 b 的一个公约数。既然是公约数，它肯定小于或等于它们最大的公约数，因此 g ≤ g'。

再从右边推导到左边：
因为 g'|(a-b) 且 g'|b，所以 g'|((a-b)+b)，即 g'|a。g' 既是 a 的约数，又是 b 的约数，那么 g' ≤ g。

两边结合起来：g ≤ g' 且 g' ≤ g，所以 g 必然等于 g'。证毕。

在此基础上，我们可以一直减下去：

gcd(a,b) = gcd(a-b,b) = gcd(a-2b,b) = ... = gcd(a mod b, b)

这就是欧几里得算法的核心思想。

用Python实现欧几里得算法

以55和34为例，我们计算一下：

gcd(55,34) = gcd(55 mod 34, 34) = gcd(21,34)
= gcd(34 mod 21, 21) = gcd(13,21)
= gcd(21 mod 13, 13) = gcd(8,13)
= gcd(13 mod 8, 8) = gcd(5,8)
= gcd(8 mod 5, 5) = gcd(3,5)
= gcd(5 mod 3, 3) = gcd(2,3)
= gcd(3 mod 2, 2) = gcd(1,2)
= gcd(2 mod 1, 1) = gcd(0,1)
= 1

翻译成代码，简单到令人难以置信：

def gcd(a, b):
    if (a, b) == (0, 0):
        raise ValueError("a and b cannot be both 0")
    if b == 0:
        return a
    return gcd(b, a % b)

为了直观地观察函数调用的过程，我在 trae 的帮助下加了一个 show_stack 方法——不必纠结它的实现细节，只要能看清调用栈即可：

import inspect
def gcd(a, b):
    if (a, b) == (0, 0):
        raise ValueError("a and b cannot be both 0")
    if b == 0:
        show_stack()
        return a
    return gcd(b, a % b)

def show_stack():
    for frame_info in inspect.stack()[:][1:]:
        frame = frame_info.frame
        args = []
        for name in frame.f_code.co_varnames[:frame.f_code.co_argcount]:
            if name in frame.f_locals:
                args.append(f"{name}={frame.f_locals[name]}")
        print(f"{frame_info.function}({', '.join(args)})")

if __name__ == "__main__":
    gcd(55, 34)

保存为 calc_gcd.py，运行 python3 calc_gcd.py，输出如下：

gcd(a=1, b=0)
gcd(a=2, b=1)
gcd(a=3, b=2)
gcd(a=5, b=3)
gcd(a=8, b=5)
gcd(a=13, b=8)
gcd(a=21, b=13)
gcd(a=34, b=21)
gcd(a=55, b=34)
()

看到没有？这些调用顺序倒过来，就是完整的计算路径。

验证一下

我们可以通过画图来验证。下面这段代码会调用欧几里得算法并生成一张图表：

import matplotlib.pyplot as plt

def gcd(a, b):
    if (a, b) == (0, 0):
        raise ValueError("a and b cannot be both 0")
    if b == 0:
        return a
    return gcd(b, a % b)

def plot_gcd_results(nums, gcd_results, b):
    plt.figure(figsize=(12, 8))
    plt.bar(nums, gcd_results, color='skyblue', edgecolor='black')
    plt.xlabel('a', fontsize=12)
    plt.ylabel('GCD(a, %d)' % b, fontsize=12)
    plt.title('GCD(a, %d) for a from %d to %d' % (b, nums[0], nums[-1]), fontsize=14)
    plt.xticks(nums)
    plt.yticks(range(max(gcd_results) + 1))
    plt.grid(axis='y', linestyle='--')
    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    b = 4
    nums = range(5 * b + 1)
    gcd_results = [gcd(num, b) for num in nums]
    plot_gcd_results(nums, gcd_results, b)

运行结果如下：

可以看到，gcd(a,4) 的值确实以4为周期反复出现（4,1,2,1...），与前面的分析完全一致。感兴趣的话，也可以把 b 改成其他数字试试，这里就不再一一展示了。

参考资料

• A Friendly Introduction to Number Theory 中的第五章（在 Chapter 1~6 里可以看到第一章到第六章的内容）