Assignment:
a) When we write a=mb+r in the Euclidean algorithm, call the number m a multiplier. How do the multipliers influence how long it takes the Euclidean algorithm to run?
b) For which multipliers will the Euclidean algorithm take as long as possible to run?
c) For two steps, three steps, and four steps, find the smallest pair of numbers for which the Euclidean algorithm requires this number of steps.
d) What are the numbers which appear in c?
e) Show that the numbers in c grow exponentially in size: there is a number Beta > 1 so that if the euclidean algorithm on (a,b) takes k steps then a and b are both larger than Beta^k.
Provide complete and step by step solution for the question and show calculations and use formulas.