[377] ユークリッドのアルゴリズム
'
[377] ユークリッドのアルゴリズム
ユークリッドのアルゴリズムという、素因数分解の困難な場合に有効な最大公約数の求め方があります。
2つの自然数の最大公約数を求めるとき、まず、(大きい数)÷(小さい数) を計算し、
余りが出たら、(割る数)÷(余り) の計算を割りきれるまで繰り返します。
割り切れたら、そのときの「割る数」 すなわち直前の「余り」が求める最大公約数になります。
例えば、247 と 91 の場合、
247÷91=2 余り 65 ,91÷65=1 余り 26 ,65÷26=2 余り 13 ,26÷13=2 となって、
4回の割り算で最大公約数 13 を得ます。
では、この方法で、12回の割り算でやっと最大公約数を求められる2つの自然数で最小の組は?
★ 解答説明は こちら です。