最大公約数（GCD）計算 — ユークリッドの互除法

この最大公約数計算は、ユークリッドの互除法で 2 つの整数の最大公約数を求め、整数論やプログラミングの授業で示されるとおりに、すべての割り算の手順を表示します。拡張アルゴリズムにより、ax + by = gcd(a, b) を満たすベズー係数 x、y と、2 数が互いに素のときのモジュラ逆元も求めます。整数を追加すれば、リスト全体をまとめて計算できます。

使い方

1. 2 つの整数 a と b を入力します。
2. 必要なら、最大公約数と最小公倍数に含める整数をさらに並べます。
3. 最大公約数を確認し、表で互除法の手順をたどります。
4. ベズー係数やモジュラ逆元は、ディオファントス方程式や暗号の演習に使います。

計算式

gcd(a, b) = gcd(b, a mod b)、余りが 0 になるまで繰り返す

各ステップで、大きい方の数を小さい方で割った余りに置き換え、最後の 0 でない余りが最大公約数です。手順を逆にたどると、a·x + b·y = gcd(a, b) を満たす整数 x、y が得られ、これがベズーの等式です。また lcm(a, b) = |a × b| ÷ gcd(a, b) です。

計算例

a = 1071、b = 462 の場合、1071 = 2 × 462 + 147、462 = 3 × 147 + 21、147 = 7 × 21 + 0 です。最後の 0 でない余りから gcd = 21 になります。逆に代入すると 21 = 1071 × (−3) + 462 × 7 なので x = −3、y = 7、最小公倍数は 1071 × 462 ÷ 21 = 23,562 です。