if $a,b \in \mathbb{Z}$, $a>b>0$, $b<2^n$, then in the Euclidean algorithm for $\gcd(a,b)$ the number of steps(divisions) is not more than $2n$. I'd love your help with proving that if $a,b \in \mathbb{Z}$, $a>b>0$, $b<2^n$, then in the Euclidean algorithm for $\gcd(a,b)$ the number of steps(divisions) is not more than $2n$.
I tried to use the fact that the remainders $r_1,r_2,..$ in this algorithm satisfy $r_{i+2}<\frac{r_i}{2}$, but it doesn't really help.
Any suggestions?
Thanks a lot!
 A: These are the crucial steps (for a modified division algorithm where $q$ is the nearest integer to the $b/a$):
$$
\forall i:~
r_{i+1} \le \frac{r_i}{2}
\quad
\implies
\quad
\forall i:~
r_{i} \le 2^{-i}r_0
\quad
\implies
\quad
r_{n} \le 2^{-n}b<1
$$
I'm assuming $r_0=\min(a,b)\le b <2^n$,
and that each $r_i$ is the signed residue
with smallest magnitude.
For Fibbonacci numbers
$b=F_k=\frac{(1+\sqrt5)^k-(1-\sqrt5)^k}{2^k\sqrt5}$
and $a=F_{k-1}$ (representing a worst case analysis),
if we start with $b=q_0a+r_0$,
then we find $q_i=1~(\forall i)$, $r_0=F_k-F_{k-1}=F_{k-2}$,
and by induction, $r_i=F_{k-i}-F_{k-i-1}=F_{k-i-2}$.
This shows that the algorithm terminates when $i=k-2$.
However, for $k$ large,
$\log_2F_k\approx0.694241k-0.16096$ (using the dominating term).
This furnishes an example where $b<2^n$
(for $n=\lceil0.694241k-0.16096\rceil$)
requires $k-2>n$ steps, still much better than
the $2n$ apparently required by the regular division algorithm.
For the regular division algorithm, where each integral quotient $q$
is the greatest integer less than or equal to the rational quotient
-- also called the (mathematical) floor function
(which is asymmetric, unlike its analogue in most
computer language implementations, which is an odd function),
and each remainder $r$ is non-negative,
say we start and end as follows:
$$
\eqalign{
 a &=q_0\, b +r_0 &\qquad 0< r_0<b<2^n\\
 b &=q_1\,r_0+r_1 &\qquad 0< r_1<r_0\\
r_0&=q_2\,r_1+r_2 &\qquad 0< r_2<r_1\\
   &~\vdots \\
r_{m-2}&=q_m\,r_{m-1}+r_m &\qquad 0< r_m<r_{m-1}\\
r_{m-1}&=q_{m+1}\,r_m
}
$$
Now the worst case (slowest) "decay" of $\{r_k\}_{k=0}^m$
is also the best case (fastest) "growth" of $\{r_m,r_{m-1},\dots,r_0\}$.
But we also know that it cannot be the case that $r_k=r_{k-1}-1$
for all $m\ge k\ge 0$ (and $m>1$). This is because as soon as $r_k$ gets so close to $r_{k-1}$ as $r_{k-1}-1$ we are at the "antepenultimate" step,
i.e., the next remainder, $r_{k+1}$, will be one, the GCD. A graceful argument will in fact show that, in the worst case, the remainders $r_k$ decay by a factor of the golden ratio, $\phi=\frac{1+\sqrt5}{2}$, here as well, i.e. $r_k < \phi^{-k}r_0$. Since $\phi^2=\frac{3+\sqrt5}{2}>2$, we get the fact you mention in your OP, and an analogous argument to mine above gives us the bound with $2n$.
A: If you know that $r_{i+2} < \frac{r_i}{2}$ than this is easy.
You can prove by induction that $r_{i+2k}< \frac{r_i}{2^k}$. Also, exactly the same way you prove that $r_{i+2} < \frac{r_i}{2}$ you can prove that $r_{2} < \frac{b}{2}$.
Then, 
$$r_{2n} < \frac{r_2}{2^{n-1}}< \frac{b}{2^n} <1 \,.$$
