最大公約数の求め方を完全攻略！すだれ算からユークリッド互除法まで

算数や数学のつまずきポイントとして挙げられることが多い「最大公約数」。分数の約分や通分はもちろん、高校数学の整数問題、さらには情報科学のアルゴリズム学習に至るまで、あらゆる場面で基礎となる極めて重要な概念です。

計算自体はシンプルに見えるものの、「すだれ算（連除法）」や「素因数分解」、桁数が大きいときに威力を発揮する「ユークリッドの互除法」など、扱う数値の桁数や問題の条件によって最適な解法が異なります。各解法の手順と使い分けのコツを整理し、小学生の基礎学習から高校数学、大人の学び直しまで役立つ決定版として分かりやすく解説します。

📌 【この記事の重要ポイントまとめ】

• 要点1：最大公約数（GCD）は「共通する約数の中で最も大きい数」であり、すだれ算・素因数分解・ユークリッドの互除法の3大アプローチで確実に攻略できる。
• 要点2：3つの数の計算では「すべてを同時に割り切れる素数だけを使う」ルールを徹底し、最小公倍数（LCM）との混同を防ぐことがミス撲滅の鍵になる。
• 要点3：2桁〜3桁前半なら「すだれ算」、文字式や論理的整理なら「素因数分解」、4桁以上の巨大な数なら「ユークリッドの互除法」と状況に応じて使い分けるのが最も効率的。

【基礎知識】最大公約数（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であるため、12と18の最大公約数は「6」となります。

ここで多くの学習者が混乱するのが、最小公倍数（LCM: Least Common Multiple）との違いです。最大公約数は「割る数（元の数より小さくなる、または等しい）」であるのに対し、最小公倍数は「共通して割り切れる倍数のうち最小のもの（元の数より大きくなる、または等しい）」を指します。12と18の最小公倍数は「36」です。

また、関連して頻出する「約数の個数の求め方」は、数値を素因数分解したときの各指数に1を足して掛け合わせることで導き出せます。構造を整理して捉えることが、整数問題全体の理解を深める近道です。

【小学生も一瞬で解ける】すだれ算（連除法）のやり方と計算手順

最大公約数を最も視覚的かつスピーディーに求める手法が、学校の授業や中学受験でも定番の「すだれ算（連除法）」です。割り算の筆算を上下逆さまにしたような枠を書き、共通の素数で割り進めていきます。

例として「24」と「36」の最大公約数をすだれ算で求めてみましょう。

【ステップ1】2つの数を並べて書き、下向きの割り算記号を書く。
【ステップ2】両方の数を同時に割り切れる素数（ここでは2）で割り、商を下に書く。
【ステップ3】商である「12」と「18」をさらに共通の素数（2）で割る。
【ステップ4】商である「6」と「9」をさらに共通の素数（3）で割る。
【ステップ5】一番下の商が「2」と「3」になり、これ以上共通の数で割れなくなったら終了。

このとき、左側に並んだ割った数をすべて掛け合わせた値が最大公約数です。

最大公約数 ＝ 2 × 2 × 3 ＝ 12

左側の数字だけを掛けるのが最大公約数、左側の数字と一番下の商まで「L字型」にすべて掛け合わせるのが最小公倍数（2 × 2 × 3 × 2 × 3 ＝ 72）となります。この明確なビジュアルの違いを覚えるだけで、計算ミスは劇的に減少します。

【中学数学・受験の王道】素因数分解を使った最大公約数の求め方

中学校以降の数学や、文字式を含む応用問題で基本となるのが素因数分解を用いたアプローチです。数を素数の掛け算の形に分解し、共通して含まれる素数の最小乗数を抽出します。

例として「60」と「84」の最大公約数を計算します。

・60を素因数分解：2² × 3¹ × 5¹
・84を素因数分解：2² × 3¹ × 7¹

共通して含まれる素因数に注目すると、「2」は両方に2乗（2²）含まれており、「3」は両方に1乗（3¹）含まれています。「5」と「7」は片方にしかありません。

したがって、共通する最小の指数を取り出して掛け算します。

最大公約数 ＝ 2² × 3¹ ＝ 12

この手法を理解しておくと、共通の約数が「1」しかない状態、すなわち「互いに素（coprime）」である条件も一目で判断できます。最大公約数が1である2つの整数は「互いに素」と呼ばれ、整数論や確率の証明問題における必須知識です。

【高校数学・大数対応】ユークリッドの互除法のやり方と仕組み

3桁や4桁を超える大きな数同士の最大公約数を求めるとき、すだれ算や素因数分解では「何で割り切れるのか」を見つけるだけで膨大な時間がかかります。そこで登場するのが、高校数学の「数学A（整数の性質）」で学ぶユークリッドの互除法です。

互除法の原理はシンプルで、「2つの自然数 A, B（A > B）について、A を B で割った余りを R とすると、A と B の最大公約数は B と R の最大公約数に等しい」という性質を利用します。余りが0になるまで割り算を繰り返すだけで、確実に答えに到達できます。

例として、パッと見では素因数が分からない「323」と「247」の最大公約数を求めてみます。

第1段階：323 ÷ 247 ＝ 1 余り 76
第2段階：247 ÷ 76 ＝ 3 余り 19
第3段階：76 ÷ 19 ＝ 4 余り 0

余りが「0」になったときの割る数、すなわち「19」が最大公約数となります。

323は「17 × 19」、247は「13 × 19」という一見して気付きにくい素数の組み合わせですが、互除法を使えば割り算を3回行うだけで誰でも正確に導き出せます。情報工学や暗号理論（RSA暗号など）の土台としても活用されるアルゴリズムです。

【応用編】3つの数の最大公約数を求める手順と注意点

数が3つ以上に増えた場合、計算手順に特有の落とし穴が存在します。特にすだれ算を用いる際、最小公倍数のルールと混同してしまうケースが多発しています。

【3つの数のすだれ算：重要ルール】
・最大公約数を求めるときは、「3つの数すべてを同時に割り切れる素数」でのみ割る。
・1つでも割り切れない数が出た時点で計算を終了する。

たとえば「24」「60」「84」の3つの数の最大公約数を解く場合：

1. 3つの数すべてが「2」で割れる → 商は 12, 30, 42
2. 再び3つの数すべてが「2」で割れる → 商は 6, 15, 21
3. 3つの数すべてが「3」で割れる → 商は 2, 5, 7
4. 「2, 5, 7」を同時に割り切れる数は「1」以外に存在しないため終了。

最大公約数 ＝ 2 × 2 × 3 ＝ 12

最小公倍数の計算では「2つの数だけでも割れれば続行する」というルールがありますが、最大公約数では「全員共通」が絶対条件です。この違いを明確に意識することがケアレスミス防止の鉄則です。

【実践ドリル】理解度をチェックする最大公約数の計算問題

身につけた解法を定着させるために、厳選した3つの練習問題に挑戦してみましょう。

【問題1】標準的な2つの数
「54」と「72」の最大公約数を求めなさい。

【問題2】3つの数の応用
「36」「90」「126」の最大公約数を求めなさい。

【問題3】桁数が大きい整数（互除法）
「493」と「391」の最大公約数を求めなさい。

---

【解答と解説】

【問題1の解答：18】
すだれ算で解く場合：54と72を2で割ると「27と36」、3で割ると「9と12」、さらに3で割ると「3と4」になります。
計算式：2 × 3 × 3 ＝ 18

【問題2の解答：18】
素因数分解を活用する場合：
・36 ＝ 2² × 3²
・90 ＝ 2¹ × 3² × 5¹
・126 ＝ 2¹ × 3² × 7¹
共通する素因数は「2¹」と「3²」なので、2 × 9 ＝ 18

【問題3の解答：17】
ユークリッドの互除法を活用する場合：
・493 ÷ 391 ＝ 1 余り 102
・391 ÷ 102 ＝ 3 余り 85
・102 ÷ 85 ＝ 1 余り 17
・85 ÷ 17 ＝ 5 余り 0
余りが0になったときの割る数である17が正解です。

【最大公約数の求め方】に関するよくある質問（FAQ）

Q1：最大公約数を表す「GCD」とは何の略ですか？
A1：英語の「Greatest Common Divisor」の頭文字を取った略称です。プログラミング言語の標準ライブラリ（Pythonの`math.gcd()`など）でも関数名として一般的に採用されています。

Q2：「互いに素」とはどのような関係のことですか？
A2：2つ以上の整数の公約数が「1」しか存在しない状態を指します。たとえば「8（2³）」と「9（3²）」はどちらも合成数ですが、共通の約数が1のみであるため「8と9は互いに素」となります。

Q3：すだれ算とユークリッドの互除法はどちらを使うのが有利ですか？
A3：2桁〜3桁前半程度の小さな数値であれば、直感的に計算できる「すだれ算」が圧倒的に早いです。一方、3桁後半〜4桁以上の数や、素因数に見当がつかない大きな数同士の場合は「ユークリッドの互除法」が最も確実で計算負担が少なくなります。

Q4：最大公約数と最小公倍数の間には公式のような関係性がありますか？
A4：2つの自然数 A, B について、「A × B ＝ 最大公約数(GCD) × 最小公倍数(LCM)」という恒等式が成り立ちます。片方が分かればもう片方を掛け算と割り算だけで逆算できるため、検算や応用問題で非常に重宝します。

まとめ：数字の規模や目的に応じた最適な計算法のマスターへ

最大公約数の計算は、単なる暗記ではなく「数の構造」を理解するための第一歩です。日常的な計算やテスト対策であればすだれ算（連除法）を確実に使いこなし、理論的な発展学習には素因数分解、桁数の大きい難問にはユークリッドの互除法を使い分ける戦略が効果を発揮します。

各解法の仕組みと長所を正しく把握し、問題の数値規模に合わせて最適な解法を選択できる柔軟な計算力を身につけていきましょう。 （出典: 最大 公約 数 求め 方（Yahoo!ニュース））