扩展欧几里得算法计算器 — 求gcd(a,b)和贝祖系数
我们的扩展欧几里得算法计算器不仅求gcd(a, b)，还求满足恒等式a×x + b×y = gcd(a, b)的整数x和y——即贝祖系数，对任意大的输入均以BigInt精度计算。它是本站模乘法逆元计算器以及无数其他数论算法的直接驱动引擎。
快速解答
本计算器使用扩展欧几里得算法，以精确的BigInt精度求gcd(a, b)以及满足a×x + b×y = gcd(a, b)的整数x和y。
输入a和b，然后点击计算。
如何使用 扩展欧几里得算法计算器 — gcd + 贝祖系数
- 1
输入两个整数a和b。
- 2
点击'计算'求gcd(a, b)以及贝祖系数x和y。
- 3
验证结果：a × x + b × y始终等于计算出的gcd。
为什么使用 扩展欧几里得算法计算器 — gcd + 贝祖系数？
普通的欧几里得算法通过重复除法求gcd(a, b)，但扩展版本在每一步都跟踪额外的记录，因此到算法结束时，它也将该gcd表示为原始a和b的线性组合——满足a×x + b×y = gcd(a, b)的整数x和y，这是贝祖恒等式所保证存在的结果。这不仅仅是一个数学趣闻：这些系数正是计算模乘法逆元、求解线性丢番图方程和实现RSA密钥生成所需要的。
常见问题
相关工具
模乘法逆元计算器 — 在线求解 ax ≡ 1 (mod m)
使用扩展欧几里得算法求a模m的模乘法逆元。免费计算器，提供BigInt精度和存在性检查。
中国剩余定理计算器 — 求解模系统
使用中国剩余定理，为两两互质的模求解同余方程组x ≡ aᵢ (mod mᵢ)。免费计算器，提供BigInt精度。
模幂运算计算器 — 在线快速bᵉ mod m
使用快速平方乘幂运算，计算任意大指数的bᵉ mod m。免费计算器，提供BigInt精度，是密码学的核心工具。
连分数计算器 — 在线展开与求值
将任意小数或分数展开为其连分数项[a₀; a₁, a₂, ...]，并查看每个渐近分数。免费计算器，提供精确的BigInt精度。