Remainders of Euclidean Algorithms

Let b = r_0, r_1, r_2, ... be the successive remainders in the Euclidean Algorithm applied to a and b. Show that every 2 steps reduces the remainder by at least one half. In other words, verify that r_{i+2} < (1/2)r_{i}, for every i = 0,1,2,.... Conclude that the Euclidean algorithm terminates in at most 2log_{2}(b) steps, where log_2 is the logarithm to the base 2.

In particular, show that the number of steps is at most seven times the number of digits of b. [Hint: What is the value of log_{2}(10)].

© SolutionLibrary Inc. 9836dcf9d7