擴展歐幾里得演算法（extended Euclidean algorithm）

歐幾里得演算法（輾轉相除法）用一個古老技巧求兩數的最大公因數：反覆把較大的數換成它對較小數的餘數：gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6。擴展版做同樣的下降，但同時追蹤如何把這個 gcd 寫成兩個原始數的組合。它回傳的不只是 g = gcd(a, b)，還有一對整數 x、y，使得 a*x + b*y = g。這些係數正是你計算模反元素與求解中國餘數定理所需的東西。

為何這樣的 x、y 存在、又如何求得？貝祖恆等式（Bezout's identity）保證存在整數 x、y 使 a*x + b*y = gcd(a, b)。擴展演算法靠倒推遞迴來建出它們：在基底情形 gcd(g, 0) = g，你有 g = g*1 + 0*0，故 x = 1、y = 0。往上回推一層，若對 (b, a mod b) 的遞迴呼叫回傳係數 (x', y') 使 b*x' + (a mod b)*y' = g，由於 a mod b = a - floor(a/b)*b，一點代數就給出 (a, b) 的係數：新的 x 是 y'，新的 y 是 x' - floor(a/b)*y'。每一層只是把組合改寫成上一層的形式。以 a=48、b=18 追蹤：gcd 下降到 (6,0) 回傳 (1,0)，往上回推得到 48*(-1) + 18*(3) = -48 + 54 = 6，故 x=-1、y=3。

這很重要，因為這些係數解鎖了單純 GCD 做不到的算術。若 gcd(a, m) = 1，擴展演算法給出 x 使 a*x + m*y = 1，這表示 a*x 模 m 為 1，所以 x 就是 a 的模反元素——這是最常見的用途，也是 RSA 解密與模算術中「除法」的基石。此演算法跑 O(log(min(a,b))) 次除法步驟，與單純歐幾里得相同，因為餘數縮得很快（經典事實：每兩步至少減半）。誠實提醒：x 與 y 不唯一（可把 x 加上 b/g 的倍數、把 y 減去相對應的 a/g 倍數），且可能為負，所以要得到乾淨的模反元素，取 x mod m 落到 0..m-1 範圍。