# Euclidean algorithm

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.

© BrainMass Inc. brainmass.com October 10, 2019, 3:37 am ad1c9bdddfhttps://brainmass.com/math/discrete-math/analyses-euclidean-algorithms-427771

#### Solution Preview

** Please see the attached file for the complete solution response **

I'm attaching the solution in .docx and .pdf formats.

Example 1.

17064107 = 12758967 * 1 + 4305140

12758967 = 4305140 * 2 + 4148687

4305140 = 4148687 * 1 + 156453

4148687 = 156453 * 26 + 80909

156453 = 80909 * 1 + 75544

80909 = 75544 * 1 + 5365

75544 = 5365 * 14 + 434

5365 = 434 * 12 + 157

434 = 157 * 2 + 120

157 = 120 * 1 + 37

120 = 37 * 3 + 9

37 = 9 * 4 + 1

9 ...

#### Solution Summary

In this solution, we analyze the given Euclidean algorithms.