最大公約数の求め方

 「この最大公約数の問題解けない・・」と助けを求められて、学校では教えていないのかもと、以前書いた記事ですが再度書きます。
 解き方は「『最大公約数』ってご存じですね」をご覧ください。共通の約数を簡単に見つけられれば、私の時代学校で習った方法で見つけられるのですが、その約数が2桁や3桁の大きな素数だとすると、パット頭にその約数は思い浮かびません。そんな時も確実に解ける方法です。
 前回は2つの数の最大公約数を求めるものですが、3つ、4つと数が増えても解けます。ちょっと手間ですが、まず2つの数で最大公約数を求め、その結果と3つ目との数で最大公約数を求め、と順に4つ5つ・・と繰り返します。
 どうしてこの方法で最大公約数が求められるか・・・、それは是非あなたが考えてみてください。

se.gif