GCDは整数の計算、分数の約分、プログラミング、暗号技術などで幅広く使われる数学の基本概念です。
最大公約数という言葉を知っていても、なぜ求める必要があるのか、ユークリッドの互除法がなぜ速いのか、LCMである最小公倍数とは何が違うのかまで理解している方は少なくないでしょうか。
この記事ではGCDの意味から求め方、公式、具体例、応用場面までを順序よく解説します。
最大公約数の意味と基本事項
それではまずGCDと最大公約数の基本について解説していきます。
GCDが表す内容
GCDはGreatest Common Divisorの頭文字を取った略語で、日本語では最大公約数と呼ばれます。
複数の整数をすべて割り切れる数を公約数といい、そのなかで最も大きい数がGCDです。
たとえば12と18の公約数は1、2、3、6であり、最も大きい6が最大公約数になります。
GCDは複数の数に共通する最大の割り切れる単位と考えると、意味をつかみやすくなります。
英語圏ではGCFやHCFという表記が使われる場合もありますが、数学や情報処理の分野ではGCDが一般的です。
約数と公約数の関係
約数とは、ある整数を余りなく割れる正の整数を指します。
20の約数は1、2、4、5、10、20です。
一方で20と30の両方を割り切れる数は1、2、5、10であり、これらが公約数です。
そのうち最大の10が、20と30のGCDになります。
数が1つだけなら最大公約数を考える必要はほとんどありません。
GCDは2つ以上の整数を比べたときに共通する性質として使われます。
最大公約数が存在する条件
0ではない整数が1つでも含まれていれば、最大公約数を定められます。
負の整数が含まれる場合でも、通常は絶対値を使って考えます。
たとえばGCD（−12、18）は6です。
GCD（a、b）はaとbの符号ではなく、絶対値によって決まります。
そのためGCD（−12、18）とGCD（12、18）は同じ6になります。
またGCD（0、15）は15です。
0と15の両方を割り切れる正の整数は15の約数であり、最大のものは15となるためです。
最大公約数の求め方
続いては、基本的な最大公約数の求め方を確認していきます。
約数を書き出す方法
小さな整数であれば、それぞれの約数を書き出して共通する数を探す方法がわかりやすいでしょう。
たとえば24と36の最大公約数を求めます。
24の約数は1、2、3、4、6、8、12、24です。
36の約数は1、2、3、4、6、9、12、18、36です。
共通する約数は1、2、3、4、6、12なので、GCDは12です。
この方法は概念を学ぶ段階では有効ですが、数が大きくなると約数の洗い出しに時間がかかります。
計算問題では、素因数分解やユークリッドの互除法を使う場面が増えていきます。
素因数分解を使う方法
素因数分解とは、整数を素数の掛け算で表す方法です。
共通する素因数を取り出し、指数が小さいほうを掛け合わせると最大公約数を求められます。
72と120を例に見てみましょう。
72は2の3乗と3の2乗の積です。
120は2の3乗と3と5の積です。
共通する部分は2の3乗と3なので、GCDは24です。
素因数分解では、数の構造を視覚的に理解できます。
共通する素因数だけを選び、指数は小さいほうを採用することが大切です。
連続する複数の数の計算
3つ以上の整数でも、2つずつ順番にGCDを求めれば計算できます。
たとえばGCD（24、36、60）は、最初に24と36のGCDである12を求めます。
次に12と60のGCDを調べると12なので、答えは12です。
つまりGCD（24、36、60）は12となります。
この考え方は、配列のすべての要素に共通する最大公約数をプログラムで調べるときにも役立ちます。
ユークリッドの互除法の仕組み
続いては、効率よく計算できるユークリッドの互除法を確認していきます。
余りを利用する考え方
ユークリッドの互除法は、大きい数を小さい数で割った余りに注目する計算方法です。
2つの整数aとbがあり、aをbで割った余りをrとします。
このときGCD（a、b）とGCD（b、r）は同じになります。
余りが0になるまで割り算を繰り返せば、最後に割った数が最大公約数です。
大きな整数でも約数を列挙せずに処理できる点が、互除法の大きな強みです。
具体例による計算手順
252と105のGCDを、ユークリッドの互除法で求めます。
252を105で割ると、商は2、余りは42です。
次に105を42で割ると、商は2、余りは21です。
42を21で割ると余りは0になるため、GCDは21です。
計算の流れは、GCD（252、105）からGCD（105、42）、さらにGCD（42、21）へと移ります。
最終的な余りが0になった段階で、直前の除数である21を答えとして採用します。
筆算に慣れていれば、比較的短い手順で処理できるでしょう。
互除法が成り立つ理由
aをbで割ったとき、aはbの倍数と余りrの和で表せます。
つまりaはb×q＋rという形です。
aとbを両方割り切る数は、aからb×qを引いたrも割り切ります。
反対にbとrを両方割り切る数は、b×q＋rであるaも割り切れます。
そのため、aとbの公約数とbとrの公約数は一致します。
この性質により、余りへ置き換えても最大公約数そのものは変わりません。
GCDとLCMの違い
続いては、最大公約数と最小公倍数の違いを確認していきます。
LCMの意味
LCMはLeast Common Multipleの略語で、日本語では最小公倍数といいます。
公倍数は複数の整数に共通する倍数であり、そのなかで最も小さい正の数がLCMです。
12と18の公倍数には36、72、108などがあります。
最も小さい36が、12と18のLCMです。
GCDが共通する約数を探す概念であるのに対し、LCMは共通する倍数の最小値を探す概念です。
GCDとLCMの比較
| 項目 | GCD | LCM |
|---|---|---|
| 日本語名 | 最大公約数 | 最小公倍数 |
| 対象 | 共通して割り切れる数 | 共通する倍数 |
| 求める値 | 最も大きい公約数 | 最も小さい正の公倍数 |
| 主な用途 | 約分、分割、単位の整理 | 通分、周期、予定の重なり |
| 12と18の例 | 6 | 36 |
分数を簡単にするならGCD、異なる分母をそろえるならLCMを使うと考えると判断しやすくなります。
両者は似た名前ですが、扱う方向が反対である点に注意が必要です。
積を使った公式
0ではない2つの正の整数aとbには、GCDとLCMを結ぶ重要な関係があります。
aとbの積は、GCD（a、b）とLCM（a、b）の積に等しくなります。
LCM（a、b）はa×bをGCD（a、b）で割って求められます。
たとえば12と18では、GCDが6です。
12×18を6で割ると36となり、LCMを求められます。
片方がわかれば、もう片方を計算できるため、問題演習で役立つ公式です。
最大公約数の活用場面
続いては、最大公約数が使われる具体的な場面を確認していきます。
分数の約分
分数を最も簡単な形にするには、分子と分母をそのGCDで割ります。
たとえば84分の126は、84と126の最大公約数である42で両方を割れます。
結果は2分の3です。
小さな約数で何度も割ることもできますが、最初から最大公約数を使えば一度の計算で既約分数にできます。
約分では分子と分母を同じ整数で割ることが前提です。
同じ大きさへの分割
GCDは、複数の長さや個数を余りなく同じ単位に分けたいときにも使われます。
48cmと72cmのリボンを、余りなく同じ長さに切るケースを考えます。
最も長く切れる共通の長さは、48と72のGCDである24cmです。
余りなく分割できる最大の単位を求める問題では、GCDを使う可能性が高いでしょう。
最小の回数や最小の周期を求める問題では、LCMを検討します。
文章題では、最大、同じ長さ、余りなくという表現がGCDの手がかりになります。
プログラミングと情報技術
プログラムでは、整数演算の基本機能としてgcd関数が用意されている言語も多くあります。
比率を最簡比に直す処理、座標の格子点判定、循環処理の計算、暗号アルゴリズムなどで利用されます。
特に公開鍵暗号の基礎では、2つの数が互いに素かどうかを確認する必要があります。
互いに素とはGCDが1である2つの整数の関係です。
GCDが1かどうかの判定は、数学だけでなく情報セキュリティでも重要な役割を持ちます。
最大公約数のまとめ
最後に、GCDと最大公約数のポイントをまとめます。
GCDは複数の整数を共通して割り切れる数のうち、最も大きい数です。
小さな数では約数を書き出す方法、素因数分解、より大きな数ではユークリッドの互除法が便利でしょう。
ユークリッドの互除法では、大きい数を小さい数で割った余りへ順に置き換え、余りが0になったときの除数を答えにします。
LCMである最小公倍数とは対象が異なりますが、2数の積を通じて深い関係があります。
約分や分割の文章題では最大公約数、通分や周期の問題では最小公倍数を意識すると、適切な計算方法を選びやすくなります。
GCDの意味と互除法の流れを身につけることが、整数計算を正確かつ効率的に進める第一歩です。
