Why are Fibonacci numbers bad for Euclid's Algorithm and how to derive this upper bound on number of steps needed in general? I want to ask two things.
The first is why are consecutive Fibonacci numbers the worst case for Euclid's algorithm? I keep seeing people say it in passing and I understand that it's really bad, but how do we know it's the worst?
The second question is about an upper bound on the number of applications of the division algorithm needed to compute the GCD of two distinct positive integers. I am given a hint that it will be of the form $c \log b + d$ when $c, d$ are constants and $b$ is the smaller of the two numbers you start with. 
I have seen someone mention that it is $\frac{1}{2} \log b + 1$ but again, I don't know how to derive this and would very much appreciate a hint or push in the right direction. 
Thank you in advance!
 A: Hint:
On every iteration, $(a,b)$ is replaced by $(b,a\bmod b)$. The worst case occurs when the decrease $a-b$ is the smallest, and this occurs when the integer quotient is $b/a=1$ (so that $a\bmod b=a-b$).
By its very definition, the Fibonacci sequence has this property at every step.
Now if $F_k\le b\le F_{k-1}$ for some $k$, the number of iterations for $n$ cannot exceed $F_k$ (the worst case).
From the Binet formula, $$F_k\approx\phi^k$$ and the bound is
$$k\approx\log_\phi n.$$
A: Let's say an input to the Euclidean algorithm is a pair $(a,b)$ of natural number $a,b\in\Bbb N$ (without zero) with $a> b$. Remember that for $a_0> b_0$, the algorithm proceeds via
$$a_{i+1}=b_i,\qquad b_{i+1}=a_i\text{ mod } b_i$$
and terminates after $k$ iterations when $b_k=0$. Let $A_k$ be the set of inputs for which the algorithm terminates in exactly $k$ steps.  We show

Theorem. $A_k$ has a component-wise smallest element $(a,b)$, i.e. for all $(c,d)\in A_k$ we have $c\ge a$ and $d\ge b$.

I will give a proof, but let me first say the following: these component-wise smallest elements can be considered as the worst inputs to the Euclidean algorithm. Why? Because we expect smaller inputs to termiante earlier. But these specific minimal elements do not $-$ they are relatively small but need $k$ steps as all the other bigger elements in $A_k$ too. So these minimums are the worst when it comes to runtime relative to size.
Proof. 
The proof goes by induction. It is easy enough to see that $A_1=\{(ka,a)\mid a,k\in\Bbb N,k\ge 2\}$. Then $A_1$'s smallest element is $(2,1)$.
It is also straight forward to see that if $(a,b)\in A_k$, then $(a+b,a)\in A_{k+1}$. I claim that if $(a,b)$ is minimal in $A_k$, then $(a+b,a)$ is minimal in $A_{k+1}$. 
Let's show this by contradiction. Assume there is an element $(c,d)\in A_{k+1}$ with $c<a+b$ or $d<a$. We can exclude the last case, because one iteration of the Euclidean algorithms would generate $(d,c\text{ mod } d)\in A_k$ for which $(a,b)$ is not smaller now, in contradiction to its choice. So we have $d\ge a$ but $c<a+b$. We also see that $(c\text{ mod } d)\ge b$, which is equivalent to $c-kd\ge b$ for some $k\in\Bbb N$, especially $c-d\ge b$. But now
$$c<a+b\le d+(c-d)=c.$$
Contradiction. $\quad\square$
So we have a worst element in $A_k$ in some precise sense. And if you follow the construction of these element in the proof, you can see that they follow the generation rule of the Fibonacci numbers.
If you are familiar with the Fibonacci numbers $F_k$, then you probably know that $F_k$ grows exponentially like $\phi^k$ where $\phi$ is the golden ration $\phi\approx 1.618...$. So this construction yields an input pair with elements of minimum size $\sim\phi^k$ in $A_k$ which terminates after $k$ steps. Turn this around and you have that in the worst case for an input pair with elements of minimum size $s$, the Euclidean algorithm terminates after $\sim \log_\phi s$ steps.
A: The number of steps required to compute $\gcd(a,b)$ is given by the length$^{(*)}$ of the continued fraction of $\frac{a}{b}$. It follows that the worst-case scenario for the Euclidean algorithm is given by the convergents of $\varphi=\frac{1+\sqrt{5}}{2}=[1;1,1,1,1,\ldots]$, i.e. by consecutive Fibonacci numbers.
(*) Explanation: assuming $a>b$, a step of the Euclidean algorithm brings the couple $(a,b)$ into the couple $(b,a\pmod{b})$. On the other hand, the Gauss map $x\mapsto \frac{1}{x-\lfloor x\rfloor}$ applied to $x=\frac{a}{b}$ acts in the exactly same way. It follows that the computation of $\gcd(F_{n+1},F_n)$ requires $n$ steps since it travels the convergents $[1],[1;1],[1;1,1],\ldots$ of $\frac{F_{n+1}}{F_n}$ in the opposite direction. Additionally, $\frac{F_{n+1}}{F_n}$ is the rational number $>1$ with a continued fraction having length $n$ and the least numerator/denominator: the terms of a continued fraction, with the only exception of the very first one, cannot be smaller than $1$. It follows that when considering all the continued fractions with the same length, the minimum of $\frac{a}{b}\to |a|+|b|$ is attained by $[0;1,1,1,\ldots]$.
A: You can prove this using induction on the number of gcd() calls.
To prove: If a pair (a,b) takes n steps to compute the gcd, then

*

*a >= F_(k+2)

*b >= F_(k+1)
With one assumption a >= b

Base case n = 1, the lemma is true.
Consider the lemma to be true for n = k - 1, k > 1
Let a pair (a,b) be such that it takes k steps to compute the gcd.
Hence (b, a mod b) will take k - 1 steps.
Thus b >= F_(k+1) ... by hypothesis
And a mod b >= F_(k)
Now, a = b×q + a mod b >= b + a mod b >= F_(k+1) + F_(k) >= F(k+2)
Hence we have proven that consequentive fibonacci numbers are the worst case. More specifically, they are the least of the numbers to take a certain arbitrary number of steps.
