最大公約数 – 求め方 | ２つの整数や３つの整数について具体例を用いて解説
" 最大公約数 – 求め方 “について解説をしています。
具体的な整数を例に使って、求める方法を２つ述べています。
はじめに表紙に記している18と24の最大公約数を求めた方法を解説し、それから３つのときの求め方を説明します。
最大公約数の求め方を理解するためには、公約数というものの定義を押さえておくと良いかと思います。
整数 a と b について、a と b の両方を割り切る自然数を「整数 a と b の公約数」と定義します。
3 つ以上についても、それら全てを割り切る自然数が公約数です。
最大公約数 – 求め方: 2つのときについて
18と24を例に、
最大公約数を求める方法を解説。
表紙の図で、
2) 18 24 とすだれ算を開始しました。
18 と 24 の公約数を１つもってきて、その公約数で割ってできた商を下に書きます。
2 という 18, 24 の公約数で割ったときの商は、
9 と 12 です。
今度は、9 と 12 の公約数をもってきます。
3) 9 12 というすだれ算の続きです。
再び公約数である 3 で割ったときの商を下に書きます。
3 と 4 となります。
また公約数を考えるのですが、3 と 4 の公約数は 1 しかありません。
このすだれ算ですが、公約数が 1 しかないという状況になったら、操作を終了します。
この終了のところまでくると、割る数として横に書いた公約数たちが拾い上げられたことになります。
2) 18 24
3) 9 12
だったので、拾い上げた公約数は 2 と 3 です。
最後に、これらの拾い上げた公約数たちを全て掛け合わせます。
その掛け算の値が求める最大公約数となります。
すなわち、
2 × 3 = 6 が、18 と 24 の最大公約数です。
【求め方のまとめ】
①公約数で割り続ける
②公約数が 1 しかなくなったら、すだれ算を終了する
③拾い上げた公約数たちを全て掛け合わせる
③で、全てを掛けたときの値が求める最大公約数です。
このすだれ算が表している内容について説明をしておきます。
求め方の操作が表す内容
18 = 2×32,
24 = 23×3 と素数の積の形になっています。
自然数は素数ばかりの積の形で表すことができます。
18 と 24 のどちらにも使われている素数は公約数となっています。
先ほど、公約数の 2 で割りました。
すると、
9 = 32, 12 = 22×3 となります。
そうすると、次の公約数として、もう 2 は使えないことに気づきます。
そこで、次に、どちらにも使われている 3 を公約数として考えたわけです。
9 と 12 を 3 で割ると、
3, 4 = 22 となりました。
そして、公約数が 1 しかないことから操作を終了したわけです。
このように、素数の積の形を思い描きながら、公約数たちを割る数として拾い上げていたわけです。
さらに、
90, 210, 390 という３つの整数の最大公約数を求める手順について説明をします。
3つの最大公約数の求め方
90, 210, 390 の公約数である 2 で割った商を下に書きます。
45, 105, 195 となるので、次の公約数として 3 を考えます。
3 で割ると、
15, 35, 65 なので、公約数として 5 を取れます。
5 で割ると、
3, 7, 13 となります。
これらの公約数は 1 しかありません。
公約数が 1 しかないという終了の合図となったので、ここまでで拾い上げた公約数をすべて掛け合わせます。
2×3×5 = 30 が求める最大公約数です。
90 = 30×3,
210 = 30×7,
390 = 30×13 となっているわけです。
ここまで、すだれ算を使った最大公約数の求め方について述べてきました。
ただ、この方法には問題点があります。
それは、「公約数が見つからないときに、すだれ算が開始できない」ということです。
この問題点が出てきたときのために、もう１つの最大公約数の求め方について、これから解説をします。
「228 と 817」の最大公約数を求めるということを考えます。
このときの方法の根本となる命題を１つ述べ、それを利用して求め方を説明します。
もう１つの最大公約数の求め方
【正しい命題】
自然数 b を a で割ったときの商を q, 余りを r とする。
すなわち、b = aq+r
(ただし、0≦ r < a)とする。
このとき、
a と b の最大公約数は、a と r の最大公約数に等しい。
つまり、割られる数と割る数の最大公約数は、割る数と余りの最大公約数に等しい。
この割られる数と割る数の最大公約数は、割る数と余りの最大公約数に等しいということを使い続ける方法になります。
「228 と 817」の最大公約数を例に、求め方を説明します。
大きい方の 817 を割られる数 b、228 を割る数 a として命題を使い続けます。
命題を使うためには、割り算を計算して、商と余りを求めます。
このときに、割り算を計算すれば良いので、公約数が見つからないという問題点に出くわすことがないので、気分が楽です。
その代わりに、計算が長くなってしまうこともあるので、「公約数がすぐに見つかったときは、すだれ算を使う」と、使い分けを日頃から意識しておくと良いかと思います。
操作を実行する
817÷228を計算して商と余りを確定します。
817
= 228×3+133 なので、
余りが133と分かりました。
ここで、「割られる数817と割る数228の最大公約数が、割る数228と余り133の最大公約数に等しい」という命題を使います。
817 と 228 で最大公約数を求めるよりも、より小さい数のペアで最大公約数を求めることができるわけです。
228と133の最大公約数を求めれば良いということが、命題によって分かりました。
そこで、今度は大きい方の228を b、133を割る数 a として、再び割り算を計算し、商と余りを確定させます。
228
= 133×1+95 です。
228と133の最大公約数が求める最大公約数ということでしたが、再び命題によって、割る数133と余り95の最大公約数に等しいということになります。
より小さいペヤの方が計算しやすいので、
133を b、割る数 a を 95 として、また割り算を計算して商と余りを確定させます。
133
= 95×1+38 です。
再び「割られる数と割る数の最大公約数は、割る数と余りの最大公約数に等しい」という命題を使います。
これで、95と38の最大公約数が求める最大公約数と分かりました。
そこで、また割り算を計算します。
95 = 38×2+19 となります。
さらに命題を使い、割る数38と余り19の最大公約数が求める最大公約数と分かります。
終了する合図を認識
割られる数38と割る数19で割り算を計算します。
38 = 19×2+0 となります。
余りが 0 になるときが、操作を終了するときの合図となります。
38と19の最大公約数ですが、割り切れたので、割る数19自身が最大公約数ということです。
「228 と 817」の最大公約数を言い換えて、38と19の最大公約数というところまで来ました。
そして、38と19の最大公約数が19と分かりました。
以上より、19が「228 と 817」の最大公約数です。
実際、
228 = 19×12,
817 = 19×43 となっています。
12と43の公約数は 1 しかないので、確かに最大公約数となっています。
19が公約数と気づければ、すだれ算で１回の割り算で最大公約数を求めることができたわけですが、なかなか公約数が見つからないときのための求め方になります。
【関連する記事】
■ 素数判定法
■ 5進数の小数
それでは、これで今回の記事を終了します。
読んで頂き、ありがとうございました。