欧几里得算法

对很大的数，靠分解两个数来求最大公约数会很慢。欧几里得算法用一个巧妙的招法完全绕开分解：它不断把较大的数替换为它被较小数除后所剩的余数，眼看着数字一路缩小，直到其中一个变为零。

步骤如下。要求 gcd(a, b)（设 a 大于 b），用 a 除以 b 保留余数 r。然后丢开 a，照同样办法求 gcd(b, r)，再重复。每一步余数都严格变小，于是终有某个余数变为 0 — 而最后一个非零余数就是最大公约数。其原理依据是 gcd(a, b) 等于 gcd(b, a mod b)。

这个算法已有两千多年历史，至今仍是已知最快的算法之一。它也是扩展欧几里得算法的引擎：后者不仅求出最大公约数，还把它表示成 a 与 b 的整数组合 — 这正是裴蜀等式的内容，也是求解线性丢番图方程和计算模逆元的关键一步。