ユークリッドの互除法とは？
ユークリッドの互除法は、紀元前300年ごろにギリシャの数学者ユークリッドが記した、現存する最古のアルゴリズムのひとつです。2つの整数の最大公約数（GCD）、つまり両方を余りなく割り切れる最大の数を求めます。この計算機は、任意の2つの非負整数にこのアルゴリズムを適用し、あわせて最小公倍数（LCM）も求めます。
使い方
a と b の欄に2つの数を入力して実行するだけです。メインの結果として最大公約数（GCD）を、補足の値として最小公倍数（LCM）を表示します。入力する順番は結果に影響しません — \(\gcd(48, 36)\) と \(\gcd(36, 48)\) は同じ答えになります。負の数は絶対値として扱われ、一方が0の場合はもう一方の数がそのままGCDになります。
計算式の仕組み
このアルゴリズムは、ひとつのシンプルな性質に基づいています。a と b の公約数は、その余り a mod b も必ず割り切る、という点です。そこで、大きいほうの数を余りに置き換える操作を繰り返します。
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$ そして基底条件は \(\gcd(a, 0) = a\) です。
各ステップで数は急速に小さくなるため、非常に大きな値でもわずか数回の計算で答えが出ます。最小公倍数（LCM）は $$\operatorname{lcm}(a,b) = \frac{a \times b}{\gcd(a,b)}$$ で求められます。
計算例
\(\gcd(48, 36)\) を求めてみましょう。
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$ $$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = 12$$
よって最大公約数は12、最小公倍数は $$\operatorname{lcm} = \frac{48 \times 36}{12} = \frac{1728}{12} = 144$$ となります。
よくある質問
両方の数が0のときは？ 0と0の最大公約数は、このツールでは0と定義しています。正の公倍数が存在しないため、最小公倍数も0になります。
なぜ約数を一つずつ調べるより速いの？ すべての約数を列挙する代わりに、余りを使った近道で問題のサイズを各ステップごとに大きく縮めるからです。一般的に対数時間で処理できます。
とても大きな数でも計算できる？ はい。ユークリッドの互除法は桁数の多い数でも効率的で、必要な剰余計算の回数はごくわずかです。
