Let b = r0, r1, r2, . . . be the successive remainders in the Euclidean algorithm applied...

Let b = r0, r1, r2, . . . be the successive remainders in the Euclidean algorithm applied to a and b. Show that after every two steps, the remainder is reduced by at least one half. In other words, verify that

Conclude that the Euclidean algorithm terminates in at most 2 log2(b) steps, where log2 is the logarithm to the base 2. In particular, show that the number of steps is at most seven times the number of digits in b. [Hint. What is the value of log2(10)?]