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}$
-
0It's considered rude to formulate your question as a command. Please reformulate it as a question, and indicate what you've already thought about. – 2011-10-24
-
0Thanks for your notification. – 2011-10-24
-
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
Neither argument is terribly hard.