アルゴリズムの原理：
拡張ユークリッド互除法（Extended Euclidean Algorithm）は2つの整数 a と m の最大公約数 gcd(a, m) を計算するだけでなく、整数 x と y を見つけて、 ax + my = gcd(a, m)。
を満たします。これはベズーの等式（Bézout's identity）の応用です。
アルゴリズム手順：
- ユークリッド互除法：互除法を使用して gcd(a, m) を計算し、各ステップの商と余りを記録
- 逆代入過程：最後のステップから逆方向に代入し、各余りを a と m の線形結合で表現
- 係数を求める：最終的に係数 x と y を求め、ax + my = gcd(a, m) を満たす
モジュラ逆元（Modular Inverse）：
gcd(a, m) = 1 の場合（a と m が互いに素）、a の m を法とする乗法逆元が存在し、a-1 mod m と表記します。このとき x がモジュラ逆元で、 a × x ≡ 1 (mod m)。
x が負の場合は正の数に調整：x' = x mod m。
応用シーン：
- 暗号学：RSA アルゴリズムで秘密鍵を計算する際にモジュラ逆元が必要
- 数論問題：一次合同式 ax ≡ b (mod m) の解法
- 組合せ数学：組合せ数のモジュロ演算（Lucasの定理など）
- 競技プログラミング：モジュラ逆元を高速計算し、除算による精度問題を回避
時間計算量：
O(log min(a, m))、ユークリッド互除法と同様
ベズーの等式（Bézout's Identity）：
任意の整数 a と m に対して、整数 x と y が存在し、ax + my = gcd(a, m) が成り立ちます。これらの係数 x と y は拡張ユークリッド互除法で効率的に計算できます。