Calculatrice de Euclidean Algorithm

原理

欧几里得算法是现存最古老的仍在使用的算法（《几何原本》约公元前 300 年）：gcd(a, b) = gcd(b, a mod b)，反复迭代直到余数为零，除数即最大公约数。正确性来自「同时整除 a 与 b 的数必整除余数」。

扩展欧几里得算法回代得贝祖系数 ax + by = gcd(a, b)，这是模逆元（ modular-inverse 工具）的基础：gcd(a, m) = 1 时 a 在模 m 下的逆元即贝祖系数 x。拉梅定理保证步数不超过较小数十进制位数的 5 倍（最坏输入是相邻斐波那契数）。

使用步骤

① 输入两个正整数；② 得到 gcd、每一步带余除法与贝祖等式；③ 若要模逆元，直接读贝祖等式中 a 的系数再取模。

计算示例

gcd(1071, 462)：1071 = 2×462 + 147、462 = 3×147 + 21、147 = 7×21 + 0，共 3 步得 gcd = 21。gcd(48, 18) = 6（3 步）；gcd(240, 46) = 2 且 2 = 240×(−9) + 46×47。

注意事项

输入为 0 时 gcd(a, 0) = a；两数相等时一步即得。最坏情形（斐波那契相邻对如 610 与 981）步数 = 斐波那契下标 − 2，可用于压力测试。

常见问题

Q：为什么不用质因数分解求 gcd？A：分解大数极其困难，而辗转相除对 10^15 规模瞬时完成——这正是它在 RSA 时代依然优雅的原因。

Q：贝祖系数唯一吗？A：不唯一，相差 (b/g, −a/g) 的整数倍；扩展算法给出的是回代所得的一组（通常最小）系数。