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}$
5
$\begingroup$
elementary-number-theory
-
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