euclidean algorithm 計算ツール
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) 的整数倍；扩展算法给出的是回代所得的一组（通常最小）系数。
参考值区（同源数值校验）
gcd(1071, 462) = 21（3 步）、gcd(48, 18) = 6（3 步）、gcd(240, 46) = 2（5 步）。
euclidean algorithm 計算ツールの使い方
- 各入力欄に自分の数値を入力します — 各欄に求める値の説明があります。
- 入力すると結果は即座に更新されます。「計算」ボタンは不要です。
- 結果カードで主要な数値、手順、実務上の注意点を確認できます。
よくある質問
euclidean algorithm 計算ツールは無料ですか？
はい — Calcton の数学の計算ツールはすべて無料で、登録も不要です。入力データはブラウザ内で処理され、サーバーには送信されません。
このツールの中国語版はありますか？
はい。上の中国語版へのリンクをご利用ください。同じ計算ツールを簡体字中国語インターフェースで利用できます。
関連する計算ツール
同カテゴリのその他のツール: 数学の計算ツール一覧
数学の計算ツールについて
代数・統計・数論・日常算数のための無料オンライン数学計算ツール。二次方程式や行列から、パーセント・分数・素因数分解まで、すべてに計算式と手順を表示します。