在线辗转相除法计算器

辗转相除法（欧几里得算法）是人类已知最古老的算法之一，记载于《几何原本》（约公元前 300 年）。原理是 gcd(a, b) = gcd(b, a mod b)：用大数除以小数取余，余数替换大数，反复迭代直到余数为 0，此时的除数就是最大公约数。

把每一步的商回代，还能解出贝祖等式 ax + by = gcd(a, b) 的一组整数解（扩展欧几里得算法），这是求模逆元、解一次同余方程的基础。本工具逐步展示除法过程、统计步数，并给出贝祖系数与最小公倍数。

辗转相除法记载于欧几里得《几何原本》第七卷（约公元前 300 年），是人类已知最古老的非平凡算法之一，至今仍是所有现代数论与密码系统的地基。欧几里得当年的表述是几何的——用短尺不断去量长尺，直到恰好量尽，那把最后的尺子就是两段的公度。写成算式就是：gcd(a, b) = gcd(b, a mod b)，迭代至余数为零。

算法为什么一定正确？关键在于"公约数集合不变"：若 d 整除 a 与 b，则 d 必整除 a − qb = r；反过来，整除 b 与 r 的数也必整除 qb + r = a。所以 (a, b) 与 (b, r) 的全部公约数完全相同，最大公约数自然相同。而余数严格递减且非负，不可能无限降下去，必然在有限步内到达 0——此时另一个数就是答案。

效率有多高？1844 年拉梅（Gabriel Lame）证明：辗转相除的步数不超过较小数十进制位数的 5 倍——这是历史上第一个算法复杂度分析。最坏情形恰由相邻斐波那契数达成，因为每步商都是 1，余数只缩小一个 φ 倍。实际工程中还有更优的变体：二进制 gcd 算法只用移位和减法，适合硬件实现。用它配合 lcm，可得 a×b = gcd(a,b)×lcm(a,b)，这也是最小公倍数计算器背后的恒等式。