最大公約数と最小公倍数の求め方まとめ

約数・倍数と GCD・LCM の意味

ある整数を割り切ることができる整数を約数、ある整数を整数倍した数を倍数といいます。2つ以上の整数に共通する約数（公約数）のうち最も大きいものが最大公約数（GCD）、共通する倍数（公倍数）のうち0を除いて最も小さいものが最小公倍数（LCM）です。

たとえば 84 と 120 の場合、84 の約数は 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84、120 の約数は 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 です。共通するのは 1, 2, 3, 4, 6, 12 で、最大公約数は 12 です。公約数はすべて最大公約数 12 の約数になっている点も覚えておくと便利です。

最大公約数が 1 になる2数は「互いに素」といいます。たとえば 8 と 15 は共通の素因数を持たないので互いに素で、最小公倍数は単純な積の 120 になります。

方法1：素因数分解で求める

それぞれの数を素数の積に分解すると、最大公約数と最小公倍数の構造がはっきり見えます。84 = 2² × 3 × 7、120 = 2³ × 3 × 5 です。

最大公約数は、共通する素因数について指数の小さい方を取って掛け合わせます。2 は 2² と 2³ のうち 2²、3 は両方 1乗、7 と 5 は片方にしかないので含めません。よって 2² × 3 = 12 です。最小公倍数は、登場するすべての素因数について指数の大きい方を取ります。2³ × 3 × 5 × 7 = 840 となります。

この方法は3つ以上の数にもそのまま使えます。12 = 2² × 3、18 = 2 × 3²、30 = 2 × 3 × 5 なら、最大公約数は 2 × 3 = 6、最小公倍数は 2² × 3² × 5 = 180 です。ただし数が大きくなると素因数分解そのものに手間がかかるため、次の互除法が役立ちます。

素因数分解ができると、約数の個数もすぐに分かります。120 = 2³ × 3 × 5 なら、各指数に1を足して掛けた (3 + 1) × (1 + 1) × (1 + 1) = 16 個が約数の個数です。先ほど書き出した120の約数がちょうど16個あることと一致します。素因数分解の計算ツールでは、約数の個数・総和・約数の一覧も同時に確認できます。

• GCD：共通する素因数の、指数の小さい方を掛ける
• LCM：すべての素因数の、指数の大きい方を掛ける

方法2：連除法（すだれ算）で求める

連除法は、並べた数を共通の素数で割り続け、割った数を左側に書き出していく筆算です。小学校や中学校で習う「すだれ算」とも呼ばれます。

84 と 120 なら、まず 2 で割って 42 と 60、さらに 2 で割って 21 と 30、次に 3 で割って 7 と 10 になります。7 と 10 には 1 以外の共通の約数がないので、ここで止めます。左側の割った数を掛けた 2 × 2 × 3 = 12 が最大公約数、それに残った 7 と 10 も掛けた 12 × 7 × 10 = 840 が最小公倍数です。

3つ以上の数で最小公倍数を求めるときは、2つの数だけに共通する素数でも割り進め、割れない数はそのまま下ろす、というやり方が一般的です。この場合、最大公約数は「3つすべてを割った数」だけを掛ける点に注意が必要です。

方法3：ユークリッドの互除法で求める

ユークリッドの互除法は、「a を b で割った余りを r とすると、a と b の最大公約数は b と r の最大公約数に等しい」という性質を繰り返し使う方法です。素因数分解をしなくてよいため、大きな数でも少ない手順で答えが出ます。この性質が成り立つのは、a = bq + r と書けるとき、a と b の公約数は r = a − bq も割り切り、逆に b と r の公約数は a = bq + r も割り切るからです。つまり2つの組の公約数はまったく同じで、最大のものも一致します。

252 と 198 で試してみます。252 = 198 × 1 + 54、198 = 54 × 3 + 36、54 = 36 × 1 + 18、36 = 18 × 2 + 0 と進み、余りが 0 になったときの割る数 18 が最大公約数です。4回の割り算で終わり、252 や 198 を素因数分解する必要はありません。

最大公約数・最小公倍数の計算ツールもこの互除法で計算しており、最初の2数について各段階の商と余りを表で確認できます。3つ以上の数は、2数ずつ順に最大公約数を求めていけば全体の最大公約数になります。

GCD × LCM ＝ a × b の関係

2つの正の整数 a と b の間には、最大公約数 × 最小公倍数 ＝ a × b という関係が成り立ちます。84 と 120 なら 12 × 840 = 10,080、84 × 120 = 10,080 で一致します。素因数分解で見ると、指数の小さい方と大きい方を両方掛ければ、結局すべての指数を足したのと同じになるためです。

この関係を使えば、最小公倍数は LCM = a × b ÷ GCD で求められます。252 と 198 なら 252 × 198 ÷ 18 = 2,772 です。互除法で最大公約数を出してから割り算するのが、大きな数の最小公倍数を求める最も手早い方法です。

ただし、この等式は2数の場合に限ります。12、18、30 の3数では GCD 6 × LCM 180 = 1,080 ですが、12 × 18 × 30 = 6,480 で一致しません。3数以上では、素因数分解か2数ずつの計算を使いましょう。

約分・通分・周期の問題での使い方

分数の約分では、分母と分子を最大公約数で割ると一度で既約分数になります。84/120 は最大公約数 12 で割って 7/10 です。通分では最小公倍数を共通の分母にすると数が最も小さく済みます。1/12 + 1/18 は 12 と 18 の最小公倍数 36 を分母にして 3/36 + 2/36 = 5/36 です。

周期が重なるタイミングも最小公倍数で求めます。12分おきに出るバスと18分おきに出るバスが同時に発車したら、次に同時に出るのは 36 分後です。反対に「ものを余りなく同じ大きさに分ける」問題は最大公約数の出番で、縦84cm・横120cmの板を余りなく正方形に切り分けるとき、最も大きい正方形は一辺 12cm、枚数は 7 × 10 = 70 枚になります。

• まとめて同時に起こる・そろう → 最小公倍数
• 余りなく等分する・最大の大きさ → 最大公約数
• 84/120 = 7/10（GCD 12 で約分）