Prove that if Euclid’s algorithm applied to the pair (u, v) takes n steps, then $u ≥ f_{n+2}$ and $v ≥ f_{n+1}$.

Question

Let $u, v \in \mathbb{Z^+}$ satisfy $u > v$. Prove that if Euclid’s algorithm applied to the pair (u, v) takes n steps, then $u ≥ f_{n+2}$ and $v ≥ f_{n+1}$.

I think that to start this proof I would first have to show that applying Euclid's Algorithm to $f_{n+1}$, $f_{n+2}$ would take $n$ steps, but when I tried to do this I wasn't sure how to apply it to a situation where there were no numbers, only variables.

Answer 1

Just use induction.

If it takes $n$ steps to computed $\gcd(u,v)$, then it takes $n-1$ steps to compute $\gcd(v,r)$, where $u=qv+r$, with $q\ge 1$. By induction, $v\ge f_{n+1}$ and $r\ge f_n$ and so $u = qv+r \ge v+r \ge f_{n+1}+f_n=f_{n+2}$.

I'll leave the base cases to you. (The crucial observation is that the last quotient is at least $2=f_3$.)

This result was used by Lamé in 1844 to prove that $n \le 5d$, where $d$ is the number of decimal digits in $b$. It is the first well-known theorem on computational complexity. It is fitting that this theorem is about the first algorithm proposed in history.

See this paper for more details:

Jeffrey Shallit, Origins of the analysis of the Euclidean algorithm, Historia Mathematica, Volume 21, Issue 4, November 1994, Pages 401–419.