ATRACTOR

Ela será tanto maior quanto menor for o número de divisões necessárias para chegarmos ao máximo divisor comum. Vamos começar com alguns exemplos e questões simples, para depois descobrirmos quais os piores casos.

Tomemos dois números, por exemplo \(69\) e \(30\) e apliquemos o algoritmo (da divisão) até termos resto \(0\). Os quocientes obtidos são \(2\) (\(2\) quadrados de lado \(30\)), \(3\) (\(3\) quadrados de lado \(9\)) e \(3\) (\(3\) quadrados de lado \(3\)): \(69=\mathbf{2}\times30+9\), \(30=\mathbf{3}\times9+3\) e \(9=\mathbf{3}\times3+0\). Geometricamente, os quocientes dão-nos o número de quadrados com um certo comprimento de lado.

Se quisermos fabricar um exemplo que dê como máximo divisor comum o mesmo número \(3\) e em que os quocientes sejam \(3\), \(1\), \(4\) em vez de \(2\), \(3\), \(3\), podemos fazê-lo facilmente, partindo do fim para o princípio: \(\mathbf{4}\times3+0=12\), \(\mathbf{1}\times12+3=15\), \(\mathbf{3}\times15+12=57\).

Neste processo, o número de quocientes dá, claro, o número de divisões e o último número a que se chega é tanto maior quanto maiores forem os quocientes escolhidos. Se, então, quisermos saber quais os mais pequenos números que exigem aquele número de divisões para chegar a \(3\) como máximo divisor comum, basta aplicarmos o processo aos quocientes \(1\), \(1\), \(2\) (o último quociente não pode ser \(1\), porque \(1\times x+0\) daria outra vez \(x\)): \(\mathbf{2}\times3+0=6\), \(\mathbf{1}\times6+3=9\), \(\mathbf{1}\times9+6=15\). O par \((15,9)\) é o menor que exige \(3\) divisões para chegar a \(3\) como máximo divisor comum.

E qual será o menor par que exige \(3\) divisões (sem especificar qual o máximo divisor comum a que se quer chegar)? Basta aplicar a ideia anterior ao máximo divisor comum \(1\) e quocientes \(1\), \(1\), \(2\): \(\mathbf{2}\times1+0=2\), \(\mathbf{1}\times2+1=3\), \(\mathbf{1}\times3+2=5\); é o par \((5,3)\)

Analogamente, o menor par que exige \(8\) divisões será obtido, fazendo: \(\mathbf{2}\times1+0=2\), \(\mathbf{1}\times2+1=3\), \(\mathbf{1}\times3+2=5\), \(\mathbf{1}\times5+3=8\), \(\mathbf{1}\times8+5=13\), \(\mathbf{1}\times13+8=21\), \(\mathbf{1}\times21+13=34\), \(\mathbf{1}\times34+21=55\), ou seja \((55,34)\).
Os pares assim obtidos (para os sucessivos números de divisões), que são os piores do ponto de vista da eficiência do algoritmo da divisão, são os pares de termos consecutivos da sucessão \(2,3,5,8,13,21,34,55,89,144,...\), que constituem os termos de ordem maior que \(2\) da sucessão dita de Fibonacci (os seus dois primeiros termos são iguais a \(1\)).