最大公約数の求め方は？

最大公約数の求め方3つの方法を確認しよう

最大公約数を求める方法は主に以下の3つがあります。まずは全体像を把握しましょう。

具体例で比較してみよう
24と36の最大公約数を、3つの方法で求めてみましょう。

• 素因数分解法
  → gcd
• ユークリッドの互除法
  36 = 24 × 1 + 12, 24 = 12 × 2 + 0 → gcd
• 連除法
  24と36を2、2、3で順次割る → gcd

どの方法でも答えは同じですが、数の大きさや個数によって効率性が変わります。この使い分けを理解することが、最大公約数を素早く正確に求めるコツです。

最大公約数とは？

最大公約数の定義

最大公約数（Greatest Common Divisor, GCD）とは、2つ以上の整数の公約数のうち最大のものです。

例えば、12と18の場合、12の約数は1, 2, 3, 4, 6, 12で、18の約数は1, 2, 3, 6, 9, 18になります。公約数（共通する約数）は1, 2, 3, 6で、この中で最大の数（つまり最大公約数）は6になります。

最大公約数は「2つの数がどの程度『関係が深い』か」を表す指標とも言えます。最大公約数が1の場合、その2つの数は「互いに素」と呼ばれ、共通の約数を持たない関係にあります。

記号と表記法

最大公約数にはいくつかの記号表記があります。

• gcd(a, b)：最も一般的な表記（Greatest Common Divisorの略）
• (a, b)：括弧を使った簡潔な表記
• GCD(a, b)：大文字での表記

例：

gcd(24, 36) = (24, 36) = GCD (24, 36) = 12

どの表記を使っても意味は同じですが、数学の文脈や教科書によって使い分けられています。最も普及しているのはgcd(a, b)の表記法です。

素因数分解による求め方

素因数分解法は最大公約数を求める最も基本的で理解しやすい方法です。

求め方の手順

1. 1. 各数を素因数分解する
2. 2. 共通する素因数を見つける
3. 3. 共通する素因数の最小指数の積を求める

具体例で確認しよう
素因数分解法を利用して、60と84の最大公約数を求めてみましょう。

ステップ1：各数を素因数分解する

• 60 = 2² × 3 × 5
• 84 = 2² × 3 × 7

ステップ2：共通する素因数を見つける

• 2：両方に含まれる（指数は共に2）
• 3：両方に含まれる（指数は共に1）
• 5：60のみに含まれる
• 7：84のみに含まれる

ステップ3：共通する素因数の最小指数の積を求める（最大公約数を計算）

共通する素因数の最小指数の積：2² × 3 = 4 × 3 = 12
これにより、60と84の最大公約数は12と求まりました。

この方法の利点は、なぜその答えになるのかが直感的に理解できることです。共通する素因数だけを取り出すという考え方は、最大公約数の本質を表しています。

ユークリッドの互除法による求め方

ユークリッドの互除法は、2つの数の最大公約数を効率的に求めるためのアルゴリズムです。約2300年前に古代ギリシャの数学者ユークリッドが考案したこの方法は、特に大きな数の最大公約数を求める際にその威力を発揮します。

互除法の原理

ユークリッドの互除法の基本原理は次の式で表されます。

gcd(a, b)= gcd(b, a mod b)

ここで「 a mod b」は「 a を bで割った余り」を意味します。この性質を利用して、最大公約数を求める問題を、より小さな数の組み合わせの最大公約数を求める問題へと帰着させていきます。この操作を繰り返し、余りが0になったとき、その時の除数が2つの数の最大公約数となります。

具体例で確認しよう
ユークリッドの互除法を利用して、252と198の最大公約数を求めてみましょう。

• 252 = 198 × 1 + 54 → gcd(252, 198) = gcd(198, 54)
• 198 = 54 × 3 + 36 → gcd(198, 54) = gcd(54, 36)
• 54 = 36 × 1 + 18 → gcd(54, 36) = gcd(36, 18)
• 36 = 18 × 2 + 0 → gcd(36, 18) = 18

互除法の原理（証明）

a と b の公約数を d とすると、a = dx、b = dy（x, y は整数）と表すことができます。このとき、a を b で割った商を q、余りを r とすると、a = qb + r と書けます。この式に a = dx、b = dy を代入すると、dx = qdy + r となり r = dx - qdy = d(x - qy)となります。

この式から、余り r も d で割り切れることがわかります。つまり、a と b の公約数は、b と r（a を b で割った余り）の公約数でもあります。したがって、a と b の最大公約数は、b と r を d で割った余りの最大公約数に等しくなります。

連除法（短除法）

連除法（短除法）は、複数の数を同時に小さな素数で割っていく視覚的な方法です。特に3つ以上の数の最大公約数を求める際に威力を発揮します。

求め方の手順：

1. 1. すべての数を小さな素数（2, 3, 5, 7...)で同時に割る
2. 2. 割り切れなくなったら次の素数を試す
3. 3. すべての数が互いに素になるまで繰り返す
4. 4. 使った素数の積が最大公約数

具体例で確認しよう
連除法を利用して、24と36と60の最大公約数を求めてみましょう。

1. 1. 24と36と60はすべて2で同時に割り切れるので2で割る。
   すると、3つの整数は12, 18, 30となる。
2. 2. 12と18と30はすべて2で同時に割り切れるので2で割る。
   すると、3つの整数は6, 9, 15となる。
3. 3. 6と9と15はすべて3で同時に割り切れるので3で割る。
   すると、3つの整数は2, 3, 5となる。
4. 4. 2と3と5を同時に割り切る素数は存在しないので、ここまでに使った素数の積
   2 × 2 × 3 = 12 が24と36と60の最大公約数である。

連除法の利点として、まず視覚的で理解しやすいことが挙げられます。また、3つ以上の数に対応でき、何個の数でも同時に処理可能な点も大きな魅力です。さらに段階的に進むため、計算ミスを見つけやすく、間違いが起こりにくいという特徴もあります。

一方で限界もあります。大きな素因数がある場合、例えば17や19のような素数が含まれていると、それらを見つけることが困難になります。また、数が大きくなると素数での割り切りを判断することが難しくなるため、大きな数にも不向きです。効率性の面では、ユークリッドの互除法に比べて計算量が多くなる場合があることも考慮すべき点です。

応用と発展

3つ以上の数の最大公約数

3つ以上の数の最大公約数は、gcd(a, b, c) = gcd(gcd(a, b), c)という性質を利用して段階的に計算できます。

具体例で確認しよう

gcd(a, b, c) = gcd(gcd (a, b), c)の性質を利用して、48と18と21の最大公約数を求めてみましょう。

1. 1. gcd(48, 18)を素因数分解法を使って求める。
   48 = 2⁴ × 3, 18 = 2 × 3²より、最大公約数は 2 × 3 = 6 である。
2. 2. gcd(6, 21)を素因数分解法を使って求める。
   6 = 2 × 3, 21 = 3 × 7より、最大公約数は3である。
3. 3. 1. 2. より、48と18と21の最大公約数は3である。

この方法は4つ以上の数にも同様に適用できます。ただし、連除法を使った方が一度に処理できるため効率的な場合もあります。

最大公約数と最小公倍数

最大公約数と最小公倍数（Least Common Multiple, LCM）は密接な関係にあり、以下の重要な公式で結びつけられます。

a × b = gcd(a, b) × lcm(a, b)

この公式は、2つの数の積が、その最大公約数と最小公倍数の積に等しいことを示しています。この関係を利用することで、一方の値を求めれば、もう一方の値を簡単に計算することができます。

具体例で確認しよう
24と36の最大公約数と最小公倍数を求めて、上記の公式が成り立つことを確認してみましょう。

• 最大公約数 (gcd)
  
  • 24と36の最大公約数は12です。(前述の例で確認済み)
• 最小公倍数 (lcm)
  
  • 24の倍数：24, 48, 72, 96, ...
  • 36の倍数：36, 72, 108, ...
  • 24と36の最小公倍数は72です。

公式の検証:

a × b = 24 × 36 = 864

gcd(a, b) × lcm(a, b)=12 × 72 = 864

両方の計算結果が一致し、公式が成り立つことが確認できました。

実用的な応用例

最大公約数は数学の問題だけでなく、日常生活の様々な場面で活用されています。

• タイルの配置問題:
  縦60cm、横84cmの長方形を正方形のタイルで隙間なく敷き詰める場合、使える正方形タイルの最大の一辺の長さは gcd(60, 84)=12(cm)です。
• 周期の問題:
  AさんとBさんがそれぞれ8日周期、12日周期で同じ店に来るとき、2人が再び同じ日に出会うのは lcm(8, 12) = 24日後です。また、gcd(8,12) = 4は、両者の周期が 4日ごとの共通のリズム（最小単位） で繰り返されていることを示します。
• コンピュータサイエンス:
  
  • 暗号理論（RSA暗号など）
  • アルゴリズムの最適化
  • データ構造の設計
• 音楽理論:
  音程や和音の協和性は、周波数比の最大公約数と関係があります。

これらの例からも分かるように、最大公約数は抽象的な数学概念ではなく、私たちの身の回りの現象を理解し、問題を解決するための実用的なツールなのです。

まとめ｜最大公約数（GCD）の意味と大事なポイント

最大公約数は「2つ以上の整数が共通にもつ約数のうち最大のもの」
→ 互いに素（GCD=1）かどうかの判定や、最小公倍数の計算の土台になる。

求め方は3通りを使い分け

素因数分解法：小〜中くらいの数に有効。共通する素因数の“最小の指数”だけ掛け合わせる。

ユークリッドの互除法：大きな数に最速。割り算を繰り返し、余りが0になった時の除数が答え。

連除法（短除法）：3個以上を同時に処理しやすい。左に並べた素数の積がGCD。

関連する便利な関係式

GCD と LCM：a × b = gcd(a, b) × lcm(a, b)。どちらか一方が分かればもう一方を即計算。

3個以上のとき：gcd(a, b, c)は gcd(gcd(a, b), c)のように段階計算で求められる。

ただ実際の学習では、

• 素因数分解で “最小の指数” を取り忘れる／最大公倍数と混同する
• 互除法で余り計算を誤る、あるいは途中で止めてしまう
• 連除法で割り切れなくなっても止めず、使った素数の積を取り違える

といった壁に直面する高校生は多いです。そんなときに役立つのが進研ゼミのAI質問機能（お試し無料）。

AI質問の特徴

問題を撮影するだけ！
勉強中にわからない数学の問題を撮影すると、すぐにヒントや解き方を丁寧に解説してくれます。

考え方や途中過程まで、ステップごとに解説
答えだけでなく、解答に至るまでのステップをわかりやすく提示。追加解説まで丁寧に説明してくれます。

AI質問機能を活用することで、定期テストや入試の対策に向けて、理解の“穴”をすぐに埋めることに役立ちます。「進研ゼミ」は以下より無料で体験いただけます（スマートフォン／タブレットからアプリをダウンロード）。