この記事では、「最大公約数」の意味や求め方をできるだけわかりやすく解説していきます。
最小公倍数との関係や計算問題も解説していきますので、この記事を通してぜひマスターしてくださいね。
目次
最大公約数とは？
最大公約数とは、\(2\) つ以上の自然数の公約数（= 共通の約数）の中で最大のものです。
例えば、\(32\) と \(24\) の最大公約数を考えてみましょう。
- \(32\) の約数
\(\underline{1}\), \(\underline{2}\), \(\underline{4}\), \(\underline{8}\), \(16\), \(32\) - \(24\) の約数
\(\underline{1}\), \(\underline{2}\), \(3\), \(\underline{4}\), \(6\), \(\underline{8}\), \(12\), \(24\)
\(32\) と \(24\) の公約数（共通の約数）は \(\underline{1}, \underline{2}, \underline{4}, \underline{8}\) です。
これらのうち最大のもの（最大公約数）は \(\color{red}{8}\) となります。
最大公約数の求め方
このように、それぞれの約数をすべて並べればもちろん最大公約数がわかりますが、毎回すべての約数を調べるのは大変ですよね。
ここでは、より素早く最大公約数を求める方法を \(2\) つご紹介します。
【求め方①】すだれ算（L字の筆算）
\(1\) つ目の求め方は、「すだれ算」と呼ばれるL字の筆算です。
\(2\) つ以上の自然数を同じ数で同時に割り算し、それ以上割れなくなったら割り算を終了します。
そして、L字の縦の部分だけをかけ算すると最大公約数が求められます。
L字の横の部分に残った数同士は同じ数で割れないため、「互いに素である」と表現することがあります。
L字の筆算による方法は、\(3\) つ、\(4\) つと複数の自然数の最大公約数を求める場合でも気軽に計算できて便利です。
しかし、扱う数字が \(3\) 桁、\(4\) 桁と大きく複雑になると、そもそも同時に割れる数を探すのが難しくなります（例：\(481\) と \(629\) など）。
そのような場合にはもう \(1\) つの方法、「ユークリッドの互除法」を活用しましょう。
【求め方②】ユークリッドの互除法
ユークリッドの互除法は、割り切れるまで、余りでお互いを割り続ける方法です。
割り切れた（= 余りが \(0\) となった）ときの除数が最大公約数となります。
この方法では、お互いを同時に割れる公約数が思い浮かばなくても、割り算していくだけで最大公約数を求められます。
最大公約数と最小公倍数の定理
最大公約数と最小公倍数には、重要で密接な次の関係があります。
\(2\) つの自然数 \(A, B\) の最大公約数が \(G\) であるとき、
\(A = Ga, B = Gb\)（\(a, b\) は互いに素な自然数）と表せ、
\(A, B\) の最小公倍数 \(L\) は
\begin{align}\color{red}{L = Gab}\end{align}
と表すことができる。
この定理は、最小公倍数は最大公約数で表現できることを示しています。
また、上記の定理を変形した次の式も、問題を解くときに便利です。
\begin{align}L = Gab = \displaystyle \frac{Ga \times Gb}{G} = \displaystyle \frac{AB}{G}\end{align}
よって、
\begin{align}\color{red}{LG = AB}\end{align}
「\(2\) 数の積」と「最大公約数」さえわかれば、わざわざL字の筆算をしなくても最小公倍数を求められるので、ぜひ覚えておいてくださいね。
最大公約数の計算問題
それでは、最大公約数の求め方を練習していきましょう。
計算問題①「2 数の最大公約数」
比較的割り算しやすそうな \(2\) 数なので、L字の筆算で求めてみましょう。
よって \(96\) と \(72\) の最大公約数は
\(2^3 \times 3 = 24\)
答え： \(24\)
計算問題②「3 数の最大公約数」
L字の筆算なら、数が \(3\) つに増えても対応できますね。
よって \(64\), \(144\), \(176\) の最大公約数は
\(2^4 = 16\)
答え： \(16\)
計算問題③「3 桁の 2 数の最大公約数」
\(2\) 数を同時に割れる数がパッと思いつかない場合は、ユークリッドの互除法を試してみましょう。
ユークリッドの互除法より、
\(456 \div 323 = 1 … 133\)
\(323 \div 133 = 2 … 57\)
\(133 \div 57 = 2 … 19\)
\(57 \div 19\) \(= 3 … 0\)
したがって、\(323\) と \(456\) の最大公約数は \(19\)
答え： \(19\)
最大公約数の応用問題
ここまでで、最大公約数の求め方は理解できたかと思います。
最後に、少しだけ難易度の高い問題にチャレンジしてみましょう。
応用問題「積と最小公倍数から 2 数を求める」
見慣れた文字ばかりなのに、思わず思考が停止してしまいますね…。
先ほど確認した、最大公約数と最小公倍数の定理を利用して、確実に整理していきましょう。
\(2\) つの自然数を \(A, B\) \((A > B)\)、
最大公約数を \(G\)、最小公倍数を \(L\) とおく。
題意より、
\(AB = 5400\)
\(L = 360\)
\(LG = AB\) より、
\(G = \displaystyle \frac{AB}{L} = \displaystyle \frac{5400}{360} = 15\)
よって
\(G = 15\)
ここで、
\(A = Ga\)
\(B = Gb\)
（\(a\) と \(b\) は互いに素な自然数）
とおける。
なお、\(A > B\) より \(a > b\)
\(L = Gab\) より、
\(360 = 15 ab\)
\(ab = 24\)
\(a\)、\(b\) は互いに素であるから、
\(a > b\) および \(ab = 24\) を満たす自然数 \((a, b)\) の組は
\((a, b) = (24, 1), (8, 3)\)
\((A, B) = (15a, 15b)\) より、
\((A, B)\)
\(= (15 \times 24, 15 \times 1), (15 \times 8, 15 \times 3)\)
\(= (360, 15), (120, 45)\)
答え： \(360\) と \(15\)、\(120\) と \(45\)
以上で応用問題も終わりです！
小学校で初めて習う最大公約数ですが、侮ることなかれ、大学入試にも度々登場します。
練習問題や応用問題を繰り返し解いて、最大公約数の求め方をマスターしてくださいね。