最大公約数と最小公倍数の求め方（ユークリッドの互除法で解説）

最大公約数(GCD、日本語では最大公約数、英語ではHCFとも呼ばれます)は、いくつかの整数すべてを余りなく割り切る最大の数です。最小公倍数(LCM)は、それらすべての整数で割り切れる最小の正の数です。たとえば12と18なら、最大公約数は6、最小公倍数は36になります。この2つは似た名前のわりに役割がまったく逆で、混同する人が意外と多い数字です。

なぜこの計算が必要になるのか

分数の通分、周期の違う予定を揃えるスケジュール調整、歯車やプーリーの歯数の比、レシピや配合の比率をきれいな整数に落とし込む作業。最大公約数と最小公倍数は、数学の授業を離れても意外なところで顔を出します。分母を揃えたいときに使うのが最小公倍数、比を約分してシンプルにしたいときに使うのが最大公約数です。この役割さえ覚えておけば、目の前の問題でどちらを求めればいいのか迷うことはなくなります。

ユークリッドの互除法

2つの整数の最大公約数を手計算で求めるなら、ユークリッドの互除法が最も速い方法です。大きい方の数をa、小さい方をbとして、次の手順を繰り返します。

1. aをbで割り、余りrを求める。
2. aをbに、bをrに置き換える。
3. rが0になったら終了。そのときのbが最大公約数。

12と18で実際にやってみます。

被除数	除数	商	余り
18	12	1	6
12	6	2	0

2行目で余りが0になったので、そのときの除数である6が12と18の最大公約数です。最小公倍数は、最大公約数さえ分かれば(12×18)÷6=36とすぐに計算できます。分数の1/12と1/18を足し算するときも、この36が共通の分母(最小公分母)になります。1/12は3/36に、1/18は2/36に直せるので、足し合わせると5/36です。逆に12/18のような分数を約分したいときは、最大公約数の6で分子と分母を割れば2/3まで簡単にできます。

GCD×LCMは a×b と一致する、ただし2つの数までの話

12と18の場合、6×36=216、12×18=216で、確かにぴったり一致します。最大公約数と最小公倍数を求めたあとの検算として、この関係は便利です。

ただし、この等式が成り立つのはちょうど2つの整数を対象にしたときだけです。3つ以上の数になると、GCD(a,b,c)×LCM(a,b,c)はa×b×cと一致するとは限りません。「2つの数で成り立ったのだから3つでも同じはず」と考えて計算を進めてしまう人は少なくありませんが、これは典型的な誤りです。3つ以上の数を扱うときは、この等式に頼らず、最大公約数と最小公倍数をそれぞれ別々に計算する必要があります。

3つ以上の数を扱う場合

スケジュールの例: あるタスクが4日ごとに、別のタスクが6日ごとに、さらに別のタスクが15日ごとに繰り返されるとします。3つが同じ日に重なるのはいつでしょうか。答えはLCM(4,6,15)です。まずLCM(4,6)=12を求め、次にLCM(12,15)を計算します。GCD(12,15)=3なので、LCM(12,15)=(12×15)÷3=60です。つまり60日ごとに3つのタスクが同じ日に重なります。

比を約分する例: 36、60、84という3つの数の最大公約数を求めたいとします。まずGCD(36,60)=12を求め、次にGCD(12,84)を計算すると、これも12です。したがってGCD(36,60,84)=12となります。これは、材料の分量を最小の整数比まで落として料理のレシピを縮小したり、比率データをきれいな整数の組み合わせに整理したりするときに役立つ計算です。

素因数分解という別解

ユークリッドの互除法以外に、素因数分解を使う方法もあります。3つ以上の数を扱うときや、途中経過を目で確認したいときに向いています。

12を素因数分解すると2²×3、18は2×3²です。最大公約数を求めるには、共通して現れる素因数について、指数が低い方を選びます。2は両方に含まれ、指数の低い方は2¹、3も両方に含まれ、指数の低い方は3¹なので、2×3=6が最大公約数です。最小公倍数を求めるには逆に、どちらかに現れる素因数すべてについて、指数が高い方を選びます。2²×3²=4×9=36が最小公倍数です。ユークリッドの互除法で求めた結果(GCD 6、LCM 36)とぴったり一致しており、どちらの方法でも同じ答えにたどり着くことが確認できます。

実例:歯車の比

歯数48の歯車と歯数18の歯車が噛み合っているとします。この2つの歯数の最大公約数はGCD(48,18)=6なので、歯数の比は48÷6:18÷6=8:3まで単純化できます。

では、この2つの歯車が最初の位置関係にぴったり戻ってくるのは何回転後でしょうか。答えを出すのが最小公倍数です。LCM(48,18)=144なので、48歯の歯車は144÷48=3回転、18歯の歯車は144÷18=8回転したところで、両方が同時にスタート地点の噛み合わせに戻ります。歯車設計やベルト駆動の周期を考えるとき、このような整数比の計算は避けて通れません。

自分の数値で計算する

自分の持っている数字を入力すれば、最大公約数と最小公倍数、それに素因数分解の結果までその場で確認できます。

最大公約数・最小公倍数の計算ツール

無料、登録不要、どの端末でも使えます。

フルツールを開く

よくある間違い

• 最大公約数と最小公倍数を取り違える。分母を揃えたいのか、比を約分したいのかを先に確認しないと、どちらを求めればいいのか分からなくなります。
• GCD×LCM=a×bという等式を、3つ以上の数にもそのまま当てはめてしまう。この関係は2つの数のときにしか成立しません。
• 0を含む計算での思い込み。慣習として、いずれかの数が0のとき最小公倍数は0とされます。0と正の整数に共通する正の倍数は存在しないためです。一方でGCD(0, n)はnそのものになります。
• 分数を約分する場面で、本当は最大公約数が必要なのに最小公倍数(通分に使う数)を使ってしまう、あるいはその逆をやってしまう。

よくある質問

GCD×LCM=a×bという等式は、3つ以上の数でも成り立ちますか? 成り立ちません。この等式が成立するのは、対象がちょうど2つの整数のときだけです。3つ以上の数を扱う場合、GCD(a,b,c)×LCM(a,b,c)はa×b×cと一致するとは限らないため、それぞれを別々に計算する必要があります。詳しい理由は本文の該当セクションを参照してください。

大きな2つの数の最大公約数を、手計算で最も速く求める方法は何ですか? ユークリッドの互除法です。割り算と余りの計算を繰り返すだけなので、すべての約数を書き出して比較するよりはるかに速く、数が大きくなるほどその差は開きます。

最大公約数や最小公倍数が0や負の数になることはありますか? 最大公約数と最小公倍数は、正の整数を対象に定義される概念です。実際の計算ツールでは、負の数が入力されても絶対値に置き換えて処理するのが一般的です。0が絡む場合は例外的な扱いがあり、いずれかの数が0のとき最小公倍数は慣習として0になりますが、GCD(0, n)はnになります。

共通の約数や倍数を一つずつ書き出して比べる方法とは、何が違いますか? 小さい数であれば、約数や倍数を書き出して見比べる方法でも答えにはたどり着けます。ただし数が大きくなるほど書き出す量が膨大になり、現実的ではなくなります。ユークリッドの互除法や素因数分解を使えば、同じ答えにずっと少ない手順で到達できます。