Assignment:
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)].
Provide complete and step by step solution for the question and show calculations and use formulas.