最大公約数の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つの数を両方とも割り切る公約数をすばやく見つけるために，倍数の判定法（２から１２）とその証明一覧を知っているとよいです。

練習問題

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

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

大きい数になると約数を列挙するのは大変です。そこで，工夫しましょう。$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$ が発見できた。

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

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

この方法の補足

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

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

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

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