Question
Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ performs at least $\lambda$ divisions.
Note
The variable $\phi$ is defined as $\phi := (1+\sqrt{5})/2$ where $\phi^2 = \phi + 1$, and the upper bound for the total number of divisions, $\lambda$, given by a theorem in my textbook is $\lambda \leq \log_2b/\log_2\phi + 1$.
Additionally, the values produced by Euclid's algorithm in my text given integers $a > b > 0$ is denoted as
\begin{align*}
r_0 & = a \\
r_1 & = b \\
r_0 & = r_1q_1 + r_2, \quad 1 \leq q_1 \leq r_0, \quad 1 \leq r_2 < r_1 \\
&\vdots \\
r_{i-1} & = r_iq_i + r_{i+1}, \quad 1 \leq q_i \leq r_{i-1}, \quad 1 \leq r_{i+1} < r_{i} \\
&\vdots\\
r_{\lambda-2} & = r_{\lambda-1}q_{\lambda-1} + r_\lambda, \quad 1 \leq q_{\lambda-1} \leq r_{\lambda-2}, \quad 1 \leq r_\lambda < r_{\lambda-1} \\
r_{\lambda-1} & = r_\lambda q_\lambda,
\end{align*}
where $r_\lambda$ is $\gcd(a,b)$ and the last non-zero remainder.
Current Work
If I proceed by induction, let $\lambda = 1$ be the base case. So then
$$1 \geq \log_2b/\log_2\phi \implies \phi \approx 1.62 \geq b,$$
and as $b > 0$ it is necessarily true that $b = 1$. By letting $a$ be an arbitrary integer such that $a > b=1$,
$$a = bq_1 + r_2$$
provides that $a = q_1$ for all integers $a>1$, and so for $\lambda = 1$ there exists integers $a,b$ satisfying the above conditions.
Assume that for some $\lambda \geq 1$, there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ performs at least $\lambda$ divisions.
Then for $\lambda+1$, we want $b$ to satisfy $$\lambda + 1 \geq \log_2b/\log_2\phi \implies \phi^{\lambda+1} \geq b.$$ Additionally by the upper bound on $\lambda$ given by $b$ we have that
$$\lambda+1 \leq \log_2b/\log_2\phi + 1 \implies \phi^\lambda \leq b.$$
As $b$ is an integer,
$$\lfloor\phi^\lambda\rfloor \leq b \leq \lceil\phi^{\lambda+1}\rceil.$$
From here I am not really sure where to go with this, moreover I don't know how i can apply the assumption for induction. Could anyone hint at something I may have overlooked if possible?
Best Answer
As requested:
A hint: find for small $b$ the worst cases, the pairs $(a,b)$ which need the most divisions. You need only consider $1<b<a<2b$, of course. You may notice a pattern which pairs are worst for the Euclidean algorithm.
Not for every $b$. But for $b$ in a well-known sequence.
Since the answer is found, let's elaborate:
To find the worst cases, we can employ the computer, after all, computing is what it's for:
Simple Haskell code to find worst cases
and when we ask for cases which take at least as long as the longest found so far:
Hmm, not too obvious (though if you look closely, it is discernible), let's ask for a strictly longer sequence:
Houston, we have a pattern!
The worst cases are $a = F_{n+1},\; b = F_n$ with the Fibonacci numbers $F_n$.
Now that the worst cases are identified, it remains to
Defining the Fibonacci numbers $F_0 = 0,\; F_1 = 1,\; F_{n+2} = F_{n+1} + F_n,\, n \geqslant 0$, we see that $\lambda(F_{n+2}, F_{n+1}) = \lambda(F_{n+1},F_n) + 1$, and since $F_2 = 1$ needs one division, we have $\lambda(F_{n+1},F_n) = n-1$.
We want to show that
$$\frac{\log F_n}{\log \phi} \leqslant n-1 \leqslant \frac{\log F_n}{\log \phi} + 1,$$
or
$$(n-2)\log \phi \leqslant \log F_n \leqslant (n-1)\log \phi.$$
With Binet's formula, exponentiating that yields
$$\begin{align} \phi^{n-2} &\leqslant \frac{\phi^n - \psi^n}{\phi-\psi} \leqslant \phi^{n-1}\\ \iff \phi^{n-1} + \phi^{n-3} &\leqslant \phi^n - \psi^n \leqslant \phi^n + \phi^{n-2} \end{align}$$
since $\phi\cdot\psi = -1$. Using $\phi - 1 = \frac1\phi$, the left inequality becomes
$$\psi^n \leqslant \phi^{n-1}(\phi - 1) - \phi^{n-3} = \phi^{n-2}-\phi^{n-3} = \phi^{n-4},$$
upon division by $\phi^{n-4}$
$$(-1)^{n-4}\psi^{2n-4} \leqslant 1.$$
That's certainly true for $n \geqslant 2 \iff 2n-4 \geqslant 0$, since $\lvert\psi\rvert < 1$. The right inequality becomes, after subtracting $\phi^n$
$$-\psi^n \leqslant \phi^{n-2},$$
which holds since (for $n\geqslant 2$) we have $\lvert\psi^n\rvert < 1 \leqslant \phi^{n-2}$.
So part 1 is done.
Now, why do we get the longest division chains for successive Fibonacci numbers?
Informally, we want the sequence $r_k$ of remainders to decrease as slowly as possible. If we have a large quotient $q_k = \lfloor r_{k-1}/r_k\rfloor$ in the sequence, then $r_{k+1}$ is much smaller than $r_{k-1}$, which we don't want. So the quotients should be small, ideally all should be $1$ except for the first, which doesn't matter, and the last, which is $r_{\lambda-1}/r_\lambda > 1$.
More formally, we note that the Euclidean algorithm is almost exactly the continued fraction algorithm, the steps
$$\begin{align} r_{k-1} &= q_kr_k + r_{k+1}\\ r_k &= q_{k+1}r_{k+1} + r_{k+2} \end{align}$$
become upon division by $r_k$ resp. $r_{k+1}$
$$\begin{align} \frac{r_{k-1}}{r_k} &= q_k + \frac{r_{k+1}}{r_k}\\ \frac{r_k}{r_{k+1}} &= q_{k+1} + \frac{r_{k+2}}{r_{k+1}} \end{align}$$
which is the continued fraction algorithm. The sequence of quotients in the Euclidean algorithm for $a$ and $b$ is the sequence of partial quotients in the continued fraction expansion of $\frac{a}{b}$ (the one that does not end with $1$).
Now, if we have a simple continued fraction of length $\lambda$ not ending in $1$,
$$x = [a_0,\, a_1,\, \dotsc,\, a_{\lambda-1}],$$
for the convergents
$$\frac{p_n}{q_n} = [a_0,\,a_1,\, \dotsc,\, a_n],$$
we have the recursion
$$\begin{align}p_{n+1} &= a_{n+1}\cdot p_n + p_{n-1} & q_{n+1} &= a_{n+1}\cdot q_n + q_{n-1},\end{align}$$
starting with $p_{-2} = 0,\, p_{-1} = 1,\, q_{-2} = 1,\, q_{-1} = 0$.
We are only interested in the denominators $q_n$, for which we see $q_0 = a_0\cdot q_{-1} + q_{-2} = 1$, $q_1 = a_1\cdot q_0 + q_{-1} = a_1$, and from the recursion $q_{n+1} = a_{n+1}q_n + q_{n-1}$, it is clear that $a_0$ has no influence on $q_n$, and the denominator $q_{\lambda-1}$ will be minimal if $a_1 = a_2 = \dotsc = a_{\lambda-2} = 1$ and $a_{\lambda-1} = 2$.
Choosing $a_0 = 1$, we find the convergents
$$\frac{p_0}{q_0}=\frac11,\, \frac{p_1}{q_1}=\frac21,\, \frac{p_2}{q_2}=\frac32,\, \dotsc,\,\frac{p_n}{q_n} = \frac{F_{n+2}}{F_{n+1}},\, \dotsc,\, \frac{p_{\lambda-2}}{q_{\lambda-2}}=\frac{F_{\lambda}}{F_{\lambda-1}},\, \frac{p_{\lambda-1}}{q_{\lambda-1}} = \frac{F_{\lambda+2}}{F_{\lambda+1}}$$
and thus that $F_{\lambda+1}$ is indeed the smallest $b$ for which the Euclidean algorithm can take $\lambda$ divisions.