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

'


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


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

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

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

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

　例えば、247 と 91 の場合、

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

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

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



[解答]

　最小の組を求める問題ですので、その最大公約数が１のときで、

　最後の計算は、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 が答えです。


☆ 言うまでもなく、フィボナッチ数です。

.