拡張ユークリッドアルゴリズム電卓

拡張ユークリッドアルゴリズム電卓は、2つの整数の最大公約数（GCD）を計算し、gcd(a, b) = s·a + t·b を満たす整数 s と t、すなわちベズー係数を求めます。このツールは単に GCD を計算するだけでなく、完全にアニメーション化されたステップ別の割り算テーブル、代入計算、およびモジュラ逆数の算出結果を提供します。数論の講義、暗号の研究、競技プログラミングなどに最適です。

拡張ユークリッドアルゴリズムとは？

拡張ユークリッドアルゴリズム（EEA）は、ユークリッドの古典的な GCD アルゴリズムを拡張したものです。基本的なアルゴリズムが連続的な除算によって gcd(a, b) を見つけるのに対し、拡張版では、各余りが元の入力の線形結合としてどのように表現できるかを記録する2つの整数列を同時に追跡します。

アルゴリズムの仕組み

EEA は、各除算ステップを通じて3つの値のペア (r, s, t) を保持します。

1. 初期化: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. 各ステップ: 商 q = ⌊rₙ₋₁ / rₙ⌋ を計算し、rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ を更新します
3. 余りが 0 になったら停止します。その直前の余りが gcd(a, b) です
4. 対応する s と t の値がベズー係数となります

ステップ別の例: gcd(252, 105)

結果: gcd(252, 105) = 21。ベズーの等式は 21 = 1 × 252 + (−2) × 105 となります。正確な係数については、上の電卓で実際に試してみてください。

拡張ユークリッドアルゴリズムの用途

1. モジュラ逆数（暗号学）

最も重要な用途はモジュラ逆数の計算です。gcd(a, m) = 1 である場合、ベズー係数 s は以下を満たします。

モジュラ逆数は、RSA暗号（秘密鍵の指数 d の計算）、Diffie-Hellman鍵共有、および楕円曲線暗号において不可欠です。

2. 一次ディオファントス方程式の解法

方程式 ax + by = c が整数解を持つのは、gcd(a, b) が c を割り切る場合に限られます。その場合、特解は x₀ = s·(c/d), y₀ = t·(c/d) となります（ここで d = gcd(a, b)、s, t はベズー係数）。

3. 中国の剰余定理

EEA は、中国の剰余定理の構成的証明と計算に使用されます。法（モジュロ）のモジュラ逆数を計算することで、x ≡ a₁ (mod m₁) かつ x ≡ a₂ (mod m₂) を満たす x を見つけます。

4. 分数の約分と最小公倍数

gcd(a, b) = 1 は、分数 a/b が既に既約分数であることを示します。最小公倍数は lcm(a, b) = |a·b| / gcd(a, b) で求められます。

ベズー係数は一意ではない

ベズー係数 s と t は一意に定まりません。(s, t) が一つの解である場合、任意の整数 k に対して (s + k·(b/d), t − k·(a/d)) もまた解となります（d = gcd(a, b)）。この電卓では、|s| ≤ |b/d| かつ |t| ≤ |a/d| を満たす解を返します。

時間計算量

拡張ユークリッドアルゴリズムは O(log min(a, b)) の反復回数で実行され、これは通常のユークリッドの互除法と同じです。ラメの定理によれば、ステップ数は小さい方の入力の桁数の5倍を超えることはありません。これにより、暗号アプリケーションで使用される巨大な整数に対しても極めて効率的です。

よくある質問

拡張ユークリッドアルゴリズムとは何ですか？

拡張ユークリッドアルゴリズムは、ユークリッドの GCD アルゴリズムを拡張したもので、gcd(a, b) = s·a + t·b を満たすベズー係数 s と t も同時に計算します。除算の過程で各余りが a と b の線形結合としてどのように表されるかを追跡します。

ベズー係数とは何ですか？

ベズー係数は、数論の定理であるベズーの等式によって存在が保証されている整数 s と t です。これらは gcd(a, b) = s·a + t·b を満たし、拡張ユークリッドアルゴリズムによって効率的に計算できます。モジュラ逆数の計算、ディオファントス方程式の解法、中国の剰余定理などで使用されます。

拡張ユークリッドアルゴリズムを使ってモジュラ逆数を求めるにはどうすればよいですか？

gcd(a, b) = 1（a と b が互いに素）の場合、ベズー係数 s は s·a ≡ 1 (mod b) を満たします。a mod b のモジュラ逆数は s mod b（正の値に調整したもの）です。この電卓は結果としてこれを直接表示します。

モジュラ逆数が存在しないのはどのような場合ですか？

a のモジュロ m におけるモジュラ逆数が存在するのは、gcd(a, m) = 1 の場合に限られます。gcd(a, m) > 1 の場合、a·x ≡ 1 (mod m) を満たす整数 x は存在しません。

拡張ユークリッドアルゴリズムの時間計算量はどのくらいですか？

通常のユークリッドの互除法と同じく O(log min(a, b)) 回の除算です。ラメの定理により、ステップ数は小さい方の数値の桁数の5倍以内に収まるため、非常に高速です。

参考リソース

• 拡張ユークリッドの互除法 - Wikipedia
• ベズーの等式 - Wikipedia
• モジュラ逆数 - Wikipedia