ATRACTOR

If \(a\) and \(b\) are natural numbers, with \(a<b\), and the Euclidean algorithm requires exactly \(n\) divisions to find the \(gcd(a,b)\), then \[a\geq f_{n+1}\] and \[b\geq f_{n+2}.\]

If \(a_{n}=a\) and \(a_{n+1}=b\), the \(n\) steps of the algorithm can be written with the equations \[\begin{array}{rcl} a_{n+1} & = & q_{1}a_{n}+a_{n-1},\mbox{ with }0<a_{n-1}<a_{n},\\ a_{n} & = & q_{2}a_{n-1}+a_{n-2},\mbox{ with }0<a_{n-2}<a_{n-1},\\ & & ...\\ a_{4} & = & q_{n-2}a_{3}+a_{2},\mbox{ with }0<a_{2}<a_{3},\\ a_{3} & = & q_{n-1}a_{2}+a_{1},\mbox{ with }0<a_{1}<a_{2},\\ a_{2} & = & q_{n}a_{1} \end{array}\]

Note that all the numbers that are involved are natural, and hence greater or equal to \(1\). Furthermore, the last quotient, \(q_{n}\), has to be greater or equal to \(2\), otherwise the last equation would reduce to \[a_{2}=a_{1},\] contradicting the implicit inequality in the previous equation, \(a_{1}>a_{2}\). Looking again at the equations from the last to the first (in the applet, from the final little square to the bigger ones), we get successively \[\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}\] and hence \[a_{k}\geq f_{k+1},\] \[a=a_{n}\geq f_{n+1}\] and \[b=a_{n+1}\geq f_{n+2}.\]

We know now that, if \(a\) and \(b\) don't exceed \(f_{n+2}\), then the algorithm requires not more than \(n\) steps to give the result. When \(a=f_{n+1}\) and \(b=f_{n+2}\), the algorithm uses exactly \(n\) divisions, corresponding to the recursion which defines \(\left(f_{n}\right)_{n}\) \[\begin{array}{rcl} f_{n+2} & = & f_{n+1}+f_{n},\mbox{ with }0<f_{n}<f_{n+1},\\ f_{n+1} & = & f_{n}+f_{n-1},\mbox{ with }0<f_{n-1}<f_{n},\\ & & ...\\ f_{4} & = & f_{3}+f_{2},\mbox{ with }0<f_{2}<f_{3},\\ f_{3} & = & 2f_{2} \end{array}\] we obtain \(gcd\left(f_{n+1},f_{n+2}\right)=1\) (in fact, one can prove that, for all \(n\) and \(m\), \(gcd\left(f_{n},f_{m}\right)=f_{gcd(n,m)}\)).

In this sense, the calculation of the greatest common divisor between two consecutive terms of the Fibonacci sequence corresponds to the worst case.