The worse case: Fibonacci numbers

Our major aim is to demonstrate that when the Euclidean algorithm is invoked with inputs x and y in the interval [1,N], the algorithm terminates in a mere $\hbox{$O\!\left(\log N\right)$}$ steps. Thus, the algorithm runs in linear time relative to its inputs! Of course, sometimes the algorithm terminates in only one step (e.g., when x=N and y=N-1). But we are interested in the worse case. Of all values $y\le x\le N$, which lead to the maximum n in (1) above? The answer is consecutive Fibonacci numbers!

The Fibonacci numbers are the terms in the sequence $\{F_n\}$ that are defined recursively as follows.  

$$F_n=F_{n-1}+F_{n-2},\quad\text{ with}\quad F_1=F_0=1\,.$$ (1)

Thus F₂=2, F₃=3, $F_4=5,\ldots$, F₉₉=354224848179261915075, etcetera. Suppose we apply the Euclidean algorithm (1) to x=F_n and y=F_n-1. By the very definition (2), all the quotients q_i will equal one; and the algorithm will terminate in exactly n steps.

Proposition 784

  Let F_n be the largest Fibonacci number that is less than N. Then n is the maximum number of steps required when the Euclidean algorithm is used to compute the greatest common divisor of any pair of integers x and y in [1,N] with $x\ge y$.

Proof.Exercise for the reader. $\hfill \rule{2mm}{3.2mm} \vspace{4mm}$