最大公約数の4通りの求め方

例として，$18$ と $30$ の最大公約数を計算してみましょう。

• まず，最大公約数を計算したい数 $18$ と $30$ を並べます。

• 両方ともを割り切る数を左に書いて，割った結果を下に並べます。例えば両方とも2で割れるので $18\div 2=9,30\div 2=15$ と計算します。

• 下に残った2つの数に同じことをやります。$9$ と $15$ は両方とも3で割れるので $9\div 3=3,15\div 3=5$ と計算します。 下に $3$ と $5$ が残りました。これらを両方とも割り切る $2$ 以上の整数は無いので終わりです。

• 最後に左に並んだ数をかけ合わせれば最大公約数です。つまり，最大公約数は $2\times 3=6$ です。

※2つの数を両方とも割り切る公約数をすばやく見つけるために，倍数の判定法（２から１２）とその証明一覧を知っているとよいです。

練習問題

高校数学の問題集　～最短で得点力を上げるために～ のT151では，最大公約数を計算する他の例題と計算ミスを減らすコツを紹介しています。

約数をすべて書きだせば最大公約数もすぐにわかります。

約数をすべて書き出すには

大きい数になると約数を列挙するのは大変です。そこで，工夫しましょう。$n$ の約数は「$\sqrt{n}$ 以下の正の整数でそれぞれ割り切れるか確認」すれば列挙できます。例えば，$18$ の約数を列挙したいときは次のようにします。

• $\sqrt{18}$ は $4$ より少し大きい数なので，$4$ まで「割り切れるか確認」すればよい。
• $18\div 1=18,18\div 2=9,18\div 3=6$ で $18\div 4$ は割り切れない。すべての約数 $1,18,2,9,3,6$ が発見できた。

これでも大変ですが「確実に答えを出すために，多少大変でも頑張って計算する」という姿勢も大事です。

最大公約数は素因数分解して，各素因数のべきのうち小さい方を選んだもので計算できます。例を見てみましょう。

この方法の補足

• 素因数分解が面倒なので，最大公約数を計算するときにこの方法を使うことは少ないです。
• 計算には使えなくても，最大公約数の性質の証明で活躍することもあります。例えば，最大公約数と最小公倍数の積の性質の２通りの証明の「素因数分解を用いた証明」で活躍しています。

割り算を繰り返すことで最大公約数を素早く求めるユークリッドの互除法という方法もあります。

詳しくはユークリッドの互除法の証明と不定方程式で解説しています。

ユークリッドの互除法は，数が大きくても最大公約数を素早く計算できます。最大公約数を計算するプログラムを書くならユークリッドの互除法がおすすめです。