Show that the number of steps in the Euclidean algorithm is less than $\frac{2\log b}{\log 2}$ Could anyone tell me how to prove this statement? The number of steps in the Euclidean algorithm is less than $\frac{2\log b}{\log 2}$, where  $b$ is the larger of the two numbers whose GCD is being found. 
 A: Can you show that every time you do 2 steps of the algorithm you have reduced the largest number appearing by at least a factor of 2?
A: First note that $\frac{\log b}{\log 2} = \log_2 b$, so you’re actually trying to show that the number of steps is less than $2\log_2 b$. In fact the number of steps is at most $\log_2 a+\log_2 b$, where $a$ is the smaller number, and it’s just about as easy to prove this stronger result. It follows from the fact that at each step of the Euclidean algorithm, the product of the two current numbers drops by a factor of more than $2$. That is, if $b=aq+r$, where $0\le r<a$, then $ar$, the product of the new pair of numbers, is less than $\frac12 ab$. To complete the proof, you need to do two things:


*

*Prove the fact that I just stated.

*Prove that it implies that the Euclidean algorithm takes at most $\log_2 a+\log_2 b$ steps to find $\gcd(a,b)$.


Neither argument is terribly hard.
A: I dislike both answers given. Here is a clean and straightforward calculation.
Take $a=q_1 \cdot b + r_1$ and $b=q_2 \cdot r_1 + r_2$. The key inequality will be  $r_2 <{\frac{1}{2} b}$. This follows from the fact that $r_1<b$. Indeed, if $r_1<b/2$ then automatically $r_2<r_1<b/2$; and if $r_1 > b/2$ then $q_2=1$ and $r_2=b-r_1<b/2$; and finally $r_1=b/2 \implies r_2=0<b/2$ as desired.
In the same fashion one shows that $r_4<r_2/2$ and in general $r_{2(n+1)}<r_{2n}/2$. Then we simply apply the inequalities in order to get $r_{2n}<b/2^n$.
So we have a total of $\log_2(b)$ "double-steps", which is equivalent to $2\log_2(b)$ steps.
