Euclidean Algorithm?

Question

Let b=r0, r1, r2... be the successive remainders in the Euclidean Algorithm applied to a and b. Show that every two steps reduces the remainder by at least one half. That is, r_i+2 <= ( 1/2)*r_i for all i.

Also, show that it terminates in 2*log_2(b) steps and that, in particular, show that the number of steps is at most seven times the number of digits in b.

Answer 1

Supposing that the inequality doesnt hold leads to a pretty clear contradiction. The rest of the stuff follows from that fact.

Answer 2

WARNING - Do not click Jessica R's link above. Its spam/advertising.