Explore BrainMass
Share

# Euclidean algorithm

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.

https://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.

\$2.19