欧几里得算法在线计算器

Q: 怎么使用欧几里得算法？

首先，输入整数 a 与 b（各至 10¹²，支持负数）。 然后，点击计算读取 gcd 与步骤表；扩展部分给出 s、t 与恒等式 s·a + t·b = gcd。 全程在页面内完成，结果即时更新。

什么是欧几里得算法计算器？

欧几里得算法（辗转相除法）求两个整数的最大公因数：不断用较大数除以较小数取余数，gcd(a, b) = gcd(b, a mod b)，直到余数为 0——最后一个非零余数就是 gcd。记载于欧几里得《几何原本》（约公元前 300 年）卷七。

它为什么快：每两步余数至少减半，最坏情形（相邻斐波那契数）步数约为 5 × 较小数的十进制位数——10¹² 级别的输入至多几十步。

扩展欧几里得在求 gcd 的同时回代出贝祖系数：s·a + t·b = gcd(a, b)。它给出 gcd 的线性表示，也是模逆元（模数非素数时）、解线性丢番图方程 ax + by = c、中国剩余定理的核心工具。

贝祖系数不唯一（相差 a/gcd 与 b/gcd 的倍数），扩展算法给出的是一组由回代顺序决定的规范系数。

本工具展示每一步的被除数、商、余数列表，并给出扩展步骤与最终恒等式验证。

gcd(a, b) = gcd(b, a mod b)，直到余数为 0；扩展形式 gcd(a,b) = s·a + t·b（贝祖恒等式）

支持负数输入（按绝对值计算）；步数不超过 log_φ(min(a,b))·… 约 5×位数。

如何使用欧几里得算法计算器

1
输入整数 a 与 b（各至 10¹²，支持负数）。
2
点击计算读取 gcd 与步骤表；扩展部分给出 s、t 与恒等式 s·a + t·b = gcd。
3
如需最小公倍数，用 lcm = a·b/gcd 直接换算（工具同时输出）。

计算示例

例 1gcd(1071, 462)

1071 = 2×462 + 147；462 = 3×147 + 21；147 = 7×21 + 0。三步得 gcd = 21——这也是《几何原本》原书使用的例子。lcm(1071,462) = 1071×462/21 = 23562。

例 2扩展：gcd(240, 46)

辗转得 gcd = 2；回代得 (−9)×240 + 47×46 = 2。验证：−2160 + 2162 = 2 ✓。

注意事项

步数最坏情形是相邻斐波那契数（Lamé 定理，1844）：gcd(F_{k+1}, F_k) 恰需 k − 1 步。
贝祖系数可整体平移：s′ = s + (b/g)·m、t′ = t − (a/g)·m 对任意整数 m 都满足恒等式；工具给出的系数保证 |s| ≤ b/(2g) 的规范范围。
多个数的 gcd 可以迭代：gcd(a, b, c) = gcd(gcd(a, b), c)，扩展系数需逐层合成。

常见问题

gcd(a, b) = gcd(b, a mod b)，直到余数为 0；扩展形式 gcd(a,b) = s·a + t·b（贝祖恒等式）。支持负数输入（按绝对值计算）；步数不超过 log_φ(min(a,b))·… 约 5×位数。在欧几里得算法计算器中输入参数即可按此公式自动求解，无需手工推导。

步数最坏情形是相邻斐波那契数（Lamé 定理，1844）：gcd(F_{k+1}, F_k) 恰需 k − 1 步；贝祖系数可整体平移：s′ = s + (b/g)·m、t′ = t − (a/g)·m 对任意整数 m 都满足恒等式；工具给出的系数保证 |s| ≤ b/(2g) 的规范范围。其余细节见页面注意事项一节。

gcd(1071, 462)：1071 = 2×462 + 147；462 = 3×147 + 21；147 = 7×21 + 0。三步得 gcd = 21——这也是《几何原本》原书使用的例子。lcm(1071,462) = 1071×462/21 = 23562。

首先，输入整数 a 与 b（各至 10¹²，支持负数）。然后，点击计算读取 gcd 与步骤表；扩展部分给出 s、t 与恒等式 s·a + t·b = gcd。全程在页面内完成，结果即时更新。

欧几里得算法（辗转相除法）求两个整数的最大公因数：不断用较大数除以较小数取余数，gcd(a, b) = gcd(b, a mod b)，直到余数为 0——最后一个非零余数就是 gcd。记载于欧几里得《几何原本》（约公元前 300 年）卷七。

两者同属相关计算链条：最大公约数与最小公倍数解决的是与之衔接的另一层问题。完成欧几里得算法计算后，页面底部相关推荐区可直接跳转到最大公约数与最小公倍数计算器继续演算，参数在同类工具间口径一致，交叉验证更方便。

扩展：gcd(240, 46)：辗转得 gcd = 2；回代得 (−9)×240 + 47×46 = 2。验证：−2160 + 2162 = 2 ✓。

输入整数 a 与 b（各至 10¹²。超出合理范围的输入可能导致结果无实际意义，页面注意事项一节标明了边界条件与单位口径。

本页欧几里得算法计算器与页面内的公式、示例、对照表同源，全部数字由同一套程序实时计算。可用一个已知算例代入验证：先在示例一节找到演算过程，再用相同参数在计算器中复算一遍，两次结果一致即说明口径无误。

计算过程按双精度浮点执行，结果默认保留 4 位有效小数，页面会按数值大小自动切换科学计数法。对照表中的数值与计算器输出完全同源，不存在手工四舍五入引入的偏差。

《几何原本》成书约公元前 300 年，卷七命题 1–2 描述的正是辗转相除（以几何线段「更相减损」表述）。相比同时代的其他计算程序，它是被完整、抽象、带正确性证明地记录下来的第一个算法，因此常被称为现存最古老的非平凡算法。

求 a 在模 m 下的逆元等价于解 a·x + m·y = 1（即 gcd(a, m) = 1），扩展欧几里得直接给出 x——它就是逆元（取 x mod m）。当 m 是素数时可用费马小定理 a^(m−2) 快速求逆，但扩展欧几里得对任意互素模数都有效。

参考资料

凯文内容作者Calcton 数学编辑组口径审核Calcton 编辑组交叉审核· 内容更新于 2026-09-30

负责 Calcton 的公式核对与内容撰写：每个工具的公式都注明出处，示例数字经过程序复算，健康与判定标准一律采用国际口径。

Calcton 数学编辑组：标准教科书（高中至大学低年级）与常用数学手册的公式口径。

参考来源与更新说明

本页公式与判定标准参考以下权威资料：

最后更新：2026-09-30。

免责声明：本页面提供的计算结果与说明内容仅供参考，不构成医疗、税务、投资或法律等专业建议。尽管我们力求公式与数据准确，仍可能存在误差；据此做出的任何决策，请结合专业机构意见。

欧几里得算法计算器

什么是欧几里得算法计算器？

如何使用欧几里得算法计算器

计算示例

注意事项

常见问题

参考资料

引用本页

把这个计算器嵌入到你的网站

参考来源与更新说明

什么是欧几里得算法计算器？

如何使用欧几里得算法计算器

计算示例

注意事项

常见问题

欧几里得算法的公式怎么写？

用欧几里得算法时需要注意什么？

能举个例子说明欧几里得算法吗？

怎么使用欧几里得算法？

欧几里得算法适合用在什么场景？

欧几里得算法与最大公约数与最小公倍数是什么关系？

再举一个欧几里得算法的例子？

欧几里得算法支持输入哪些数值？

怎么确认欧几里得算法的结果是准确的？

欧几里得算法计算精度如何？

欧几里得算法为什么是「最古老的算法」？

扩展欧几里得和模逆元什么关系？

参考资料

引用本页

把这个计算器嵌入到你的网站

相关计算器

参考来源与更新说明

搜索计算器