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!

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]$.

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.$$