最大公约数（GCD）计算器 — 辗转相除法

这个最大公约数计算器用辗转相除法（欧几里得算法）求两个整数的最大公约数，并按数论和编程课程的呈现方式列出每一步除法。它还运行扩展算法，给出满足 ax + by = gcd(a, b) 的贝祖系数 x 和 y，以及两数互质时的模逆元。添加更多整数，即可一次化简整个列表。

使用方法

1. 输入两个整数 a 和 b。
2. 可选：再列出要计入最大公约数和最小公倍数的整数。
3. 查看最大公约数，并在表中跟随辗转相除的各步。
4. 贝祖系数和模逆元可用于丢番图方程和密码学练习。

计算公式

gcd(a, b) = gcd(b, a mod b)，重复直到余数为 0

每一步都用较大的数除以较小的数所得的余数替换较大的数，最后一个非零余数就是最大公约数。把各步反向代入，就得到满足 a·x + b·y = gcd(a, b) 的整数 x 和 y，这就是贝祖等式；另外 lcm(a, b) = |a × b| ÷ gcd(a, b)。

示例

当 a = 1071、b = 462 时：1071 = 2 × 462 + 147，462 = 3 × 147 + 21，147 = 7 × 21 + 0。最后一个非零余数给出 gcd = 21。反向代入得 21 = 1071 × (−3) + 462 × 7，所以 x = −3，y = 7，最小公倍数为 1071 × 462 ÷ 21 = 23,562。