最大公约数
什么是最大公约数？
对于 ，若有 ，则称 为 的约数，又叫因子或因数，称 是 的倍数。对于 ，如果 既是 的约数，又是 的约数，则称 为 和 的公约数。公约数可能不止一个，我们把最大的那个称为最大公约数。记为 . 用数学语言描述就是
互素
若 ，则称 互素，或互质。即 之间没有除了 1 之外的公因子。考虑到素数是自然数的🧱，所以这也就意味着将 分解素因数之后，二者没有共同的素因子。因此它们的最小公倍数就是 .
辗转相除法
知道了什么是最大公约数，那怎么求解最大公约数呢？辗转相除法（欧几里得算法）是求解最大公约数的经典算法。不失一般性，设 ， 得
称 是 除 的商， 是 除 的余数。
Lemma
.
注，上述引理也可写为
简要证明：
先证明 的公约数是 的公约数，反之也成立。设 是 的公约数，则有
因为整数对加减乘运算封闭，所以 也是 的约数，即 的公约数。同理可证若 是 的公约数， 也是 的公约数。
记集合 为 的公约数集合， 为 的公约数集合。上面的论证说明，
所以我们得到，. 所以集合中的最大元素相等，即 的最大公约数等于 的最大公约数。
代码实现
# recursive
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
# loop
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a