最大公約数・最小公倍数計算機
2つの正の整数を入力すると、ユークリッドの互除法で最大公約数（GCD）を求め、その計算過程をステップごとに表示します。最小公倍数（LCM）も同時に算出します。
| 最大公約数（GCD） | |
|---|---|
| 最小公倍数（LCM） |
ユークリッドの互除法の計算過程
| 計算式 |
|---|
| = × + |
ユークリッドの互除法とは
ユークリッドの互除法は、2つの整数の最大公約数を求める古典的なアルゴリズムです。「大きい方の数を小さい方の数で割った余りに注目し、割る数と余りの組で同じ操作を繰り返す。余りが0になったときの割る数が最大公約数である」という手順で、大きな数同士でも少ないステップ数で正確に最大公約数を求められます。紀元前300年頃のユークリッドの著書『原論』に記載されている、現存する最古のアルゴリズムの1つとしても知られています。
最大公約数・最小公倍数計算とは
最大公約数（GCD）は2つの整数を共通で割り切れる最大の整数、最小公倍数（LCM）は2つの整数の共通の倍数のうち最小の整数です。本ツールは2つの正の整数を入力するだけで、この2つの値をユークリッドの互除法により瞬時に算出し、途中の計算過程（被除数・除数・商・余り）もステップごとに表示します。
手計算では素因数分解から共通因数を探す方法が一般的ですが、数が大きくなるほど素因数分解自体に手間がかかります。本ツールが採用するユークリッドの互除法は割り算の繰り返しだけで最大公約数を求められるため、桁数の大きな整数同士でも同じ手順で計算できます。入力は1以上の整数に限られ、0・負の数・小数を入力した場合は計算結果を表示しません。
最大公約数・最小公倍数計算の使い方
- 数値Aを入力する 最大公約数・最小公倍数を求めたい1つ目の正の整数を入力します。
- 数値Bを入力する もう1つの正の整数を入力します。AとBの大小はどちらが先でも結果は変わりません。
- 結果を確認する 最大公約数（GCD）と最小公倍数（LCM）が自動的に表示されます。
- 計算過程を確認する ユークリッドの互除法の各ステップ（被除数＝除数×商＋余り）が表として表示されるので、余りが0になるまでの手順を追えます。
使いこなすためのヒント
- 最小公倍数（LCM）は「A×B÷最大公約数（GCD）」という公式で求められます。分数の通分や、周期の異なる複数の予定が重なるタイミングを求める際によく使われます。
- 2つの数が互いに素（最大公約数が1）である場合、最小公倍数は単純にA×Bと一致します。
- ユークリッドの互除法は、大きな数同士の最大公約数を求める場合でも、素因数分解を経由するより高速に計算できるという実用上の利点があります。
- 入力する2つの数の大小は結果に影響しません。内部では自動的に大きい方の数から計算を始めます。
最大公約数・最小公倍数計算の活用シーン
分数の約分の下準備
分子と分母の最大公約数を求めれば、その数で両方を割ることで分数を約分できます。実際に約分した結果まで確認したい場合は分数計算機（約分機能つき）が便利です。
複数の周期が重なるタイミングの計算
例えば3日おきと5日おきに発生する予定が次に同じ日に重なるのは、3と5の最小公倍数である15日後です。シフトやイベントの周期調整に応用できます。
数学の宿題・試験対策の検算
手計算で求めた最大公約数・最小公倍数が正しいか、計算過程を含めてすぐに検算できます。
通分の分母を求める準備
異なる分母を持つ複数の分数を通分する際、各分母の最小公倍数が新しい共通の分母になります。
暗号や乱数生成の基礎知識の確認
RSA暗号の鍵生成など、最大公約数の計算は現代の暗号技術の基礎にも使われており、仕組みを理解する第一歩として計算過程を確認するのに役立ちます。
用語集
- 最大公約数（GCD）
- 2つ以上の整数をともに割り切れる整数（公約数）のうち、最大のものです。英語では Greatest Common Divisor と呼ばれ、GCD と略されます。
- 最小公倍数（LCM）
- 2つ以上の整数の共通の倍数（公倍数）のうち、最小のものです。英語では Least Common Multiple と呼ばれ、LCM と略されます。
- ユークリッドの互除法
- 大きい数を小さい数で割った余りに注目し、割る数と余りの組で同じ操作を繰り返して最大公約数を求めるアルゴリズムです。古代ギリシャの数学者ユークリッドの著書に由来します。
- 互いに素
- 2つの整数の最大公約数が1であることを指します。互いに素な2数の最小公倍数は、単純にその2数を掛け合わせた値になります。
- 素因数分解
- 整数を素数の積の形に分解することです。最大公約数・最小公倍数は共通する素因数の組み合わせから求めることもできますが、数が大きい場合はユークリッドの互除法の方が高速です。
- 公約数・公倍数
- 公約数は複数の整数に共通する約数、公倍数は複数の整数に共通する倍数のことです。最大公約数・最小公倍数はそれぞれの中で最大・最小のものを指します。
よくある質問
余談ですが ― 2000年以上前のアルゴリズムが今も現役である理由
ユークリッドの互除法は、紀元前300年頃に古代ギリシャの数学者ユークリッドが著した数学書『原論』（Elements）第7巻に記載されている手法です。現存する記録の中で最も古いアルゴリズムの1つとされ、2000年以上経った現代でも、コンピューターサイエンスの教科書で真っ先に紹介される代表的なアルゴリズムであり続けています。
このアルゴリズムが長く使われ続けている理由は、その計算効率の高さにあります。数学的には、ユークリッドの互除法が必要とするステップ数は、入力する数の桁数に比例する程度で済むことが証明されており（最悪のケースはフィボナッチ数列に関連する数値の組で発生します）、どれほど大きな整数同士であっても現実的な時間で最大公約数を計算できます。
現代の暗号技術（RSA暗号等）でも、鍵生成の過程で最大公約数の計算（あるいはその拡張版である拡張ユークリッドの互除法）が使われており、古代の数学的発見が現在のインターネットセキュリティを支える基盤技術の一部になっているというのは、数学の普遍性を物語る興味深い事実です。