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.
[Math] Show that the number of steps in the Euclidean algorithm is less than $\frac{2\log b}{\log 2}$
elementary-number-theory
Best Answer
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?