ユークリッドの互除法（最大公約数）計算ツール｜GCD・LCM計算

結果

最大公約数

gcd(48, 36)

最大公約数（GCD）	12
最小公倍数（LCM）	144

ユークリッドの互除法とは？

ユークリッドの互除法は、現存する最も古いアルゴリズムの一つで、紀元前300年ごろにギリシャの数学者ユークリッドが記したとされています。2つの整数の最大公約数（GCD）、つまり両方の数を余りなく割り切れる最大の数を、効率よく求める方法です。本ツールでは、GCDから直接導かれる最小公倍数（LCM）もあわせて表示します。

このツールの使い方

上の入力欄に2つの整数を入力し、計算を実行してください。本ツールは入力された値の絶対値を用い、$\gcd\!\left(a,\,b\right) = \gcd\!\left(b,\,a \bmod b\right)$ のルールを余りが0になるまで繰り返し適用します。その結果として、GCDとLCMの両方を表示します。

計算式の解説

このアルゴリズムの核心は、「大きい方の数を、それを小さい方の数で割った余りに置き換えても、2つの数の最大公約数は変わらない」という性質です。式で表すと$$\gcd\!\left(a,\,b\right) = \gcd\!\left(b,\,a \bmod b\right)$$となります。これを $b = 0$ になるまで繰り返し、最後に残った0でない値がGCDです。LCMは、2つの数の積がGCDとLCMの積に等しいという関係から、$$\operatorname{lcm}\!\left(a,\,b\right) = \frac{a \times b}{\gcd\!\left(a,\,b\right)}$$で計算できます。

2つの数を余りが0になるまで縮小する、割り算の反復ステップを示す図 — ユークリッドの互除法は、余りが0になるまで $(a,\,b)$ を $(b,\,a \bmod b)$ に置き換えます。

計算例

$\gcd(48, 36)$ を求めてみましょう。$48 \bmod 36 = 12$ なので $\gcd(36, 12)$ になります。次に $36 \bmod 12 = 0$ となるため、GCDは12です。LCMは $$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$ となります。