[答377] ユークリッドのアルゴリズム
'
[答377] ユークリッドのアルゴリズム
ユークリッドのアルゴリズムという、素因数分解の困難な場合に有効な最大公約数の求め方があります。
2つの自然数の最大公約数を求めるとき、まず、(大きい数)÷(小さい数) を計算し、
余りが出たら、(割る数)÷(余り) の計算を割りきれるまで繰り返します。
割り切れたら、そのときの「割る数」 すなわち直前の「余り」が求める最大公約数になります。
例えば、247 と 91 の場合、
247÷91=2 余り 65 ,91÷65=1 余り 26 ,65÷26=2 余り 13 ,26÷13=2 となって、
4回の割り算で最大公約数 13 を得ます。
では、この方法で、12回の割り算でやっと最大公約数を求められる2つの自然数で最小の組は?
[解答]
最小の組を求める問題ですので、その最大公約数が1のときで、
最後の計算は、2÷1=1 になるはずです。
その直前は、割る数が2で、余りが1だから、割る数を最小にするためには商が1になります。
従って、3÷2=1 余り 1 です。
更にその前は、割る数が3で、余りが2だから、5÷3=1 余り 2 です。
更にその前は、割る数が5で、余りが3だから、8÷5=1 余り 3 です。
更にその前は、割る数が8で、余りが5だから、13÷8=1 余り 5 です。
割る数を並べると、(その次が割られる数で)
1,2,3,5,8,13,21,34,55,89,144,233,377,610,……
12番目は、割る数が 233,割られる数が 377 となって、377 と 233 が答えです。
☆ 言うまでもなく、フィボナッチ数です。
.