数学の部屋へもどる
例えば、86 と 60 の最大公約数を求めるのに、ユークリッドの互除法を使うと、
次のように、最大公約数が 2だと分かるのに、4回の割り算が必要になります。
86÷60＝ 1 あまり 26
60÷26＝ 2 あまり 8
26÷8＝ 3 あまり 2
8÷2＝ 4 あまり 0 → 0 になったので終了。
◆参考 『最大公約数の求め方』
【問題１】
１から100までの整数2つの組み合わせで、最大公約数が分かるまでに、
一番割り算の回数が掛かるのは、どんな数字で、何回でしょうか。
また、その数字の組み合わせは、ある有名な数列の一部と言えますが、何でしょうか。
【問題２】
一般に、１からＮまでの整数２つであれば、最大、何回ぐらいの割り算で、最大公約数が求まるでしょうか。
【コメント】
最近、掲示板にあった、愛さんと、ヨッシーさんの回答を見ていて、思いついた問題です。
互除法は、そうとう良い方法なんだな、と改めて思いました。
◆数・数列の性質へもどる
数学の部屋へもどる