最大公约数与最小公倍数

最大公约数（Greatest Common Divisor）

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为 $(a，b)$，同样的，a，b，c 的最大公约数记为 $(a，b，c)$，多个整数的最大公约数也有同样的记号。^[1]

举例：12 与 18 的最大公因数为多少？

12 的因数有 1，2，3，4，6，12

18 的因数有 1，2，3，6，9，18

因此，12 与 18 的最大公因数为 6。

常用的求最大公约数的方法为：辗转相除法和更相减损术。

方法1: 辗转相除法

辗转相除法依赖下面的定理：^[2]

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。即：gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

使用辗转相除法求 a 和 b 的最大公约数的具体方法： 选两者中的较大者为除数（假设为 a ），较小者为被除数（假设为b），计算 a 除 b 的余数 r，当余数 r 为 0 时，取当前算式除数 b 为最大公约数，若不为 0，则用 r 取代较大者 a，重复此过程直到余数 r 为 0。

对应的 python 实现如下：

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

方法2: 更相减损术

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。^[3]

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

⚠️ 注意：这本身是一种为约分而设计的算法。

翻译成白话：可以折半的话，就折半（也就是用 2 来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

使用更相减损术求 a 和 b 的最大公约数的具体步骤：

1. 任意给定两个正整数，首先判断它们是否都是偶数，若是，则用 2 约简；若不是则执行第二步；
2. 用较大的数减去较小的数，如果得到的差恰好等于较小的数，则停止。否则，对较小的数和差值重复这个过程。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

对应的 python 实现如下：

def gcd(a, b):
    # 第 1 步, 都是偶数时用 2 约简
    f = 1
    while a % 2 == 0 and b % 2 == 0:
        a = a / 2
        b = b / 2
        f = f * 2

    # 将 a 调整为两者中的较大数
    if a < b:
        a, b = b, a

    while a - b != b:
        diff = a - b
        if diff > b:
            a = diff
        else:
            a = b
            b = diff
    return b * f

最小公倍数（Least Common Multiple）

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为 $[a，b]$，同样的，a，b，c的最小公倍数记为 $[a，b，c]$，多个整数的最小公倍数也有同样的记号。^[4]

与最小公倍数相对应的概念是最大公约数，关于最小公倍数与最大公约数，我们有这样的定理：$(a,b) \times [a,b] = a \cdot b$（a，b均为整数）。

对应的 python 实现如下：

def lcm(a, b):
    return a * b / gcd(a, b)

参考资料

1. https://baike.baidu.com/item/最大公约数/869308 ↩
2. https://baike.baidu.com/item/欧几里得算法/1647675 ↩
3. https://baike.baidu.com/item/更相减损术/449183 ↩
4. https://baike.baidu.com/item/最小公倍数/6192375 ↩