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.
Show that the number of steps in the Euclidean algorithm is less than $\frac{2\log b}{\log 2}$
-
2It probably won't hurt to remember that $2\log b/\log 2$ is the same as $2\log_2 b$. – 2011-10-25
2 Answers
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?
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, 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.