最大公约数

假设你有一块 12 英尺的木板和一块 18 英尺的木板，想把两块都裁成等长的小段，且要用尽可能长的段长而不留废料。答案是 6 英尺 — 这就是 12 与 18 的最大公约数，即能同时整除两者的最大的数。

严格地说，两个整数 a 与 b（不全为零）的最大公约数，记作 gcd(a, b)，是能同时整除二者的最大正整数。一种算法是写出二者的素因数分解，把它们共有的素数取较小的幂相乘。另一种快得多的算法是辗转相除法，即反复做带余除法。

一个有用的边界情形：对任意正数 a，有 gcd(a, 0) = a，因为每个数都整除 0，所以限制因素就是 a 本身。当 gcd(a, b) = 1 时，两数除 1 外没有公因数，称为互素（互质）— 这一条件从约分到模运算无处不在。