ある整数を割り切ることのできる整数のことを“約数“といいます。
“4”の約数であれば、“4”を割り切ることのできる”1”、”2”、”4”が約数となります。
2つ以上の整数に共通する約数のことを”公約数”といいます。
“4“と“6”の公約数を考えると？
まず、それぞれの約数を出します。
“4”の約数は、“1”、”2”、”4”です。
“6”の約数は、“1”、”2”、”3”、”6”です。
この中で、共通する約数は、“1”と“2”です。
“4”と“6”の公約数は“1”と“2”。
公約数の中で、最大のものを“最大公約数“といいます。
上記の“4”と“6”の例で言えば、公約数は“1”と“2”なので、この中で最大のものは“2”。これが最大公約数となります。
“4”と“6”のように少ない数字であれば、楽に最大公約数を求めることができます。
先ほどは、3ステップに分けて最大公約数を求めました。
- “4”と“6”、それぞれの約数を全て出す。
- “4”と“6“の約数で、共通のもの＝公約数を探す。
- 公約数の中で、最大の約数＝最大公約数を見つける。
しかし、それぞれの数字が大きくなると、約数の数も増えていきます。
これを上記3ステップでいちいち求めていると時間がかかりますし、間違える可能性も高くなります。
他に良い方法があります。
例えば“30“と“45”で考えてみましょう。
下記のプロセスに沿って計算すると、最大公約数を求められます。
- “30“と“45”の公約数の中で、“1”以外で一番小さい数字を求めます。答えは、“3”。
- “30”と“45“を上記1で求めた一番小さい公約数“3”で割ります。答えは、“10“と“15“。
- 上記1と同じく、“10”と“15”の公約数の中で、“1”以外で一番小さい公約数を求めます。答えは、“5“。
- ”10”と“15“を上記3で求めた一番小さい公約数“5“で割ります。答えは、“2“と“3”。
- “2”と“3“の公約数は“1”以外にないので、ここでこのプロセスは終わります。
このように、数字が変わっても、「“1”以外の公約数がなくなるまで続ける」と言うプロセスは変わりません。
次に、上記で求めた“1”以外の一番小さい公約数を全て掛けます。
上記の例で言えば、“3”と“5“が全てとなりますが、これを掛け合わせます。
するとなんと、それが“最大公約数“となるのです！
ステップ1で求めた“3“とステップ3で求めた“5”を掛け合わせると、
3 x 5 =15
”15”は、“30”と“45”の最大公約数です！
このプロセスを使った最大公約数の求め方を“連除法“と言うそうです。
ちなみに、この最大公約数の約数は、2つの整数の全ての公約数になります。
最大公約数を割り切れる数字は、最大公約数の元となる整数のどちらも割り切れるということになりますね。
なので、“最大公約数と全ての公約数を求めよ“と言う問題には、
まず最大公約数を求め、
次に最大公約数の約数を求める、
と言うプロセスが早い答えへのアプローチになるでしょう。
コメント