拡張ユークリッドアルゴリズム計算機 — 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を求めます。
拡張ユークリッドアルゴリズム計算機 — gcd + ベズー係数の使い方
- 1
2つの整数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精度を備えた無料計算機。