この記事は最終更新日から1年以上が経過しています。内容が古くなっているのでご注意ください。
はじめに
「最大公約数って何？」と聞かれてあなたは何と答えますか？
最大公約数とは何かという質問に答えられないと、数学の問題では多々苦労する場面があります。
しかし、最大公約数にはそれだけじゃない、大学入試に役立つ性質がたくさんあります。
今回は最大公約数について、その定義や性質、求め方などをお話します。
また、最大公約数の応用問題として、やっかいな整数問題への応用についてもバッチリ解説します！
最大公約数とは
最大公約数とは、「幾つかの数の共通の約数のうち、最大のもの」のことです。
上の図からわかる通り、28と42には1,2,7,14という共通の約数=公約数があり、その中で最も大きいのは14なので最大公約数は14です。
このように全ての約数を書き出せば、最大公約数がわかります。しかし、実際に問題を解くときにいちいち全ての約数を書き出していては時間がどれだけあっても足りません。
実はそんな悩みを解決するために、最大公約数を求める便利な計算方法があるのです。
最大公約数の求め方
最大公約数の求め方を2つ紹介します。
それは「すだれ算」と「ユークリッドの互除法」です。
求め方その① すだれ算
すだれ算では、まず最大公約数を求めたい数を横に並べて書きます。
そして、その数のどちらも割り切ることができる数を見つけて、わり算の筆算を逆向きに書いて割れる数がなくなるまでどんどん割っていきます。
28と42の例では、まず2で割ることができ、その次に7で割れます。そして2と3を共通して割り切れる数は1しか無いので終了です。
割り算が終わったら、割った数に注目します。
左側に縦に並んだ割った数（図の赤い部分）を全て掛けたものが最大公約数になるのです。
2×7=14より、28と42の最大公約数である14が求まります。
求め方その② ユークリッドの互除法
ユークリッドの互除法は、以下のような手順ですすめます。
①最大公約数を求めたい2つの数のうち、大きい数を小さい数で割る。
②割って出てきたあまりで①の計算で割る数だった数を割られる数として割る。
③そのあまりで②の計算で割る数だった数を割られる数として割る。
④③の操作をあまりが出なくなるまで繰り返す。
⑤最後の計算の割る数が求める最大公約数である。
こうして文字で書いてもわかりにくいと思うので、実際に計算例を見てみましょう
このように割る数とあまりがそれぞれ割られる数と割る数へと横にスライドしていくと考えると覚えやすいと思います。
すだれ算では最大公約数があまりに大きくなると計算が大変になってしまいます。
そういった時にはこの互除法が大活躍します。
大学入試に役立つ最大公約数の2つの性質
さて、便利な計算方法を用いて最大公約数を簡単に求められることがわかりました。
そんな最大公約数には、ただ「公約数の中で一番大きい」というだけ以上に役立つ性質があります。
公約数は最大公約数の約数
まず、最も大事な性質が、「公約数は、最大公約数の約数」ということです。
もう一度28と42の例を見て確かめてみましょう。
図から28と42の公約数は1,2,7,14です。
また、最大公約数である14の約数も1,2,7,14です。
見事に公約数と最大公約数の約数が一致しています。
これは、素因数分解を考えると当たり前だといえます。
28と42を素因数分解するとこのようになります。
そして最大公約数である14を素因数分解すると
となります。
最大公約数は、「共通する素因数を全て掛けたものの積」であり、公約数は「共通する素因数から選んだものを掛けたもの」です。
なので、最大公約数の約数に全ての公約数が含まれているのです。
素因数分解のやり方を早大生が分かりやすく解説！計算問題も付いてます
最小公倍数と最大公約数の積は元の数の積
ある整数AとBの最大公約数がa,最小公倍数をbとすると
となります。
これは、すだれ算を見るとわかります。
最大公約数は2×7
最小公倍数は2×7×2×3
28=2×7×2
42=2×7×3
掛ける順番は違えど、すだれ算の縦列を2回、横列を1回掛けることには変わりありません。
よってこれらの積は一致するのです。
