最大公約数・最小公倍数計算機
2つの正の整数を入力すると、ユークリッドの互除法で最大公約数（GCD）を求め、その計算過程をステップごとに表示します。最小公倍数（LCM）も同時に算出します。
| 最大公約数（GCD） | |
|---|---|
| 最小公倍数（LCM） |
ユークリッドの互除法の計算過程
| 計算式 |
|---|
| = × + |
ユークリッドの互除法とは
ユークリッドの互除法は、2つの整数の最大公約数を求める古典的なアルゴリズムです。「大きい方の数を小さい方の数で割った余りに注目し、割る数と余りの組で同じ操作を繰り返す。余りが0になったときの割る数が最大公約数である」という手順で、大きな数同士でも少ないステップ数で正確に最大公約数を求められます。紀元前300年頃のユークリッドの著書『原論』に記載されている、現存する最古のアルゴリズムの1つとしても知られています。
Tips
- 最小公倍数（LCM）は「A×B÷最大公約数（GCD）」という公式で求められます。分数の通分や、周期の異なる複数の予定が重なるタイミングを求める際によく使われます。
- 2つの数が互いに素（最大公約数が1）である場合、最小公倍数は単純にA×Bと一致します。
- ユークリッドの互除法は、大きな数同士の最大公約数を求める場合でも、素因数分解を経由するより高速に計算できるという実用上の利点があります。
- 入力する2つの数の大小は結果に影響しません。内部では自動的に大きい方の数から計算を始めます。
よくある質問
最大公約数は「2つの数を割り切れる整数のうち最大のもの」、最小公倍数は「2つの数の倍数のうち最小のもの」です。例えば12と18の場合、最大公約数は6、最小公倍数は36になります。
素因数分解で最大公約数を求める方法は、数が大きくなるほど素因数分解自体に時間がかかりますが、ユークリッドの互除法は割り算と余りの計算を繰り返すだけで済むため、桁数の大きな整数同士でも高速に最大公約数を求められます。
本ツールは正の整数のみに対応しています。0や負の数、小数を入力した場合は計算結果が表示されません。
本ツールは2つの数の計算に対応しています。3つ以上の場合は、2つずつ順番に計算していく（例: AとBの最大公約数を求め、その結果とCの最大公約数を求める）ことで同様に算出できます。
余談ですが ― 2000年以上前のアルゴリズムが今も現役である理由
ユークリッドの互除法は、紀元前300年頃に古代ギリシャの数学者ユークリッドが著した数学書『原論』（Elements）第7巻に記載されている手法です。現存する記録の中で最も古いアルゴリズムの1つとされ、2000年以上経った現代でも、コンピューターサイエンスの教科書で真っ先に紹介される代表的なアルゴリズムであり続けています。
このアルゴリズムが長く使われ続けている理由は、その計算効率の高さにあります。数学的には、ユークリッドの互除法が必要とするステップ数は、入力する数の桁数に比例する程度で済むことが証明されており（最悪のケースはフィボナッチ数列に関連する数値の組で発生します）、どれほど大きな整数同士であっても現実的な時間で最大公約数を計算できます。
現代の暗号技術（RSA暗号等）でも、鍵生成の過程で最大公約数の計算（あるいはその拡張版である拡張ユークリッドの互除法）が使われており、古代の数学的発見が現在のインターネットセキュリティを支える基盤技術の一部になっているというのは、数学の普遍性を物語る興味深い事実です。