ATRACTOR

Se \(a\) e \(b\) são naturais, com \(a<b\), e o algoritmo de Euclides requer exactamente \(n\) divisões para encontrar o \(mdc(a,b)\), então \[a\geq f_{n+1}\] e \[b\geq f_{n+2}.\]

Se \(a_{n}=a\) e \(a_{n+1}=b\), os \(n\) passos do algoritmo podem ser escritos pelas equações \[\begin{array}{rcl} a_{n+1} & = & q_{1}a_{n}+a_{n-1},\mbox{ com }0<a_{n-1}<a_{n},\\ a_{n} & = & q_{2}a_{n-1}+a_{n-2},\mbox{ com }0<a_{n-2}<a_{n-1},\\ & & ...\\ a_{4} & = & q_{n-2}a_{3}+a_{2},\mbox{ com }0<a_{2}<a_{3},\\ a_{3} & = & q_{n-1}a_{2}+a_{1},\mbox{ com }0<a_{1}<a_{2},\\ a_{2} & = & q_{n}a_{1} \end{array}\]

Note-se que todos os números envolvidos são naturais e portanto maiores ou iguais a \(1\). Além disso, o último quociente, \(q_{n}\), tem de ser maior ou igual a \(2\), caso contrário a última equação reduzir-se-ia a \[a_{2}=a_{1},\] contrariando a desigualdade implícita na equação anterior, \(a_{1}>a_{2}\) . Revendo as equações da última para a primeira (no applet, do quadradinho final para os maiores), obtemos sucessivamente \[\begin{array}{l} a_{2}\geq2\times1=2,\\ a_{3}\geq1\times2+1=3,\\ a_{4}\geq1\times3+2=5,\\ a_{5}\geq1\times5+3=8\\ \;\;\;\;... \end{array}\] e portanto \[a_{k}\geq f_{k+1},\] \[a=a_{n}\geq f_{n+1}\] e \[b=a_{n+1}\geq f_{n+2}.\]

Sabemos agora que, se \(a\) e \(b\) não excedem \(f_{n+2}\), então o algoritmo requer não mais que \(n\) etapas para dar o resultado. Quando \(a=f_{n+1}\) e \(b=f_{n+2}\), o algoritmo usa exactamente \(n\) divisões, correspondentes à recorrência que define \(\left(f_{n}\right)_{n}\) \[\begin{array}{rcl} f_{n+2} & = & f_{n+1}+f_{n},\mbox{ com }0<f_{n}<f_{n+1},\\ f_{n+1} & = & f_{n}+f_{n-1},\mbox{ com }0<f_{n-1}<f_{n},\\ & & ...\\ f_{4} & = & f_{3}+f_{2},\mbox{ com }0<f_{2}<f_{3},\\ f_{3} & = & 2f_{2} \end{array}\] obtendo-se \(mdc\left(f_{n+1},f_{n+2}\right)=1\) (de facto, pode provar-se que, para todo o \(n\) e \(m\), \(mdc\left(f_{n},f_{m}\right)=f_{mdc(n,m)}\)).

Neste sentido, o cálculo do máximo divisor comum entre dois termos consecutivos da sucessão de Fibonacci corresponde ao pior caso.