輾轉相除與 Bézout

輾轉相除法 (Euclidean algorithm) 求最大公因數:反覆用 $\gcd(a,b) = \gcd(b, a\bmod b)$,餘數為 0 時的除數就是答案。它快得驚人——步數與位數成正比,是最古老仍在用的演算法。

Bézout 等式:存在整數 $x, y$ 使 $ax + by = \gcd(a,b)$。把輾轉相除的每一步倒推回去就能找到(擴展歐幾里得);解不唯一:若 $(x_0, y_0)$ 是一組解、$d = \gcd(a,b)$,所有解是 $x = x_0 + k\frac{b}{d}$、$y = y_0 - k\frac{a}{d}$($k$ 為整數),$x$ 與 $y$ 要一起調整。

算例:$\gcd(48, 18)$:$48 = 2\cdot18 + 12$、$18 = 1\cdot12 + 6$、$12 = 2\cdot6$,得 6。倒推:$6 = 18 - 12 = 18 - (48 - 2\cdot18) = 3\cdot18 - 48$。$\text{lcm} = ab/\gcd$。

Bézout 是數論的萬能鑰匙:模反元素存在性、線性同餘方程可解條件、中國剩餘定理、「互質則存在 $ax\equiv1$」全由它推出;RSA 產生金鑰時,私鑰指數 $d$ 就是用擴展歐幾里得由 $e$ 與 $\varphi(N)$ 算出來的。