Explore BrainMass
Share

Explore BrainMass

    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.

    © BrainMass Inc. brainmass.com October 10, 2019, 3:37 am ad1c9bdddf
    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