[377] ユークリッドのアルゴリズム

'


[377] ユークリッドのアルゴリズム


　ユークリッドのアルゴリズムという、素因数分解の困難な場合に有効な最大公約数の求め方があります。

　２つの自然数の最大公約数を求めるとき、まず、(大きい数)÷(小さい数) を計算し、

　余りが出たら、(割る数)÷(余り) の計算を割りきれるまで繰り返します。

　割り切れたら、そのときの「割る数」 すなわち直前の「余り」が求める最大公約数になります。

　例えば、247 と 91 の場合、

　 247÷91＝2 余り 65 ，91÷65＝1 余り 26 ，65÷26＝2 余り 13 ，26÷13＝2 となって、

　４回の割り算で最大公約数 13 を得ます。

　では、この方法で、12回の割り算でやっと最大公約数を求められる２つの自然数で最小の組は？


★ 解答説明は こちら です。