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

この記事では最大公約数を求める方法を4通り紹介します。

  1. 手っ取り早く計算する方法

はぜひマスターしておきましょう。他にも,

  1. 約数をすべて書き出す方法
  2. 重要な性質を使う方法
  3. 大きい数の場合に高速に計算する方法

も解説します。

手っ取り早く計算する方法

最大公約数とは

2つの正の整数について,両方ともを割り切る数(公約数)の中で一番大きいものを最大公約数と言います。

例として,18183030 の最大公約数を計算してみましょう。

  • まず,最大公約数を計算したい数 18183030 を並べます。 pic2

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

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

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

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

練習問題

問題

1800180024002400 の最大公約数を計算せよ。

図のように計算すると,最大公約数は 100×6=600100\times 6=600 pic6

※今回は最初に100で割りました。このように最初に大きい数で割れる場合は計算が楽になります。2など小さい数ではなく100など大きい数を選ぶとよいでしょう。

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

約数をすべて書き出す方法

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

例. 18と30の最大公約数
  • 1818 の約数は,
    1,2,3,6,9,181,2,3,6,9,18
  • 3030 の約数は,
    1,2,3,5,6,10,15,301,2,3,5,6,10,15,30

両方に現れる公約数は 1,2,3,61,2,3,6 の4つ。その中で最大のものは 66 なので,最大公約数は 66

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

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

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

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

素因数分解する方法

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

例. 18と30の最大公約数
  • 1818 を素因数分解すると 2×322\times 3^2
  • 3030 を素因数分解すると 2×3×52\times 3\times 5

pic7

各素因数のべきのうち小さい方を選ぶ2×32\times 3 となる。つまり 18183030 の最大公約数は 66

この方法の補足

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

ユークリッドの互除法

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

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

例. 18と30の最大公約数
  • 30301818 で割ると
    30=18×1+1230=18\times 1+12
  • 18181212 で割ると
    18=12×1+618=12\times 1+6
  • 121266 で割ると
    12=6×212=6\times 2 となり割り切れた。

よって最大公約数は 66

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

手っ取り早い方法・素直な方法・別の命題の証明に使える方法・大きい数でも素早く計算できる方法,みんな違ってみんな良いです。