Explore BrainMass

Explore BrainMass

    Euclidean Algorithm

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

    Prove the Euclidean Algorithm:

    Let n be a natural
    number, and let q be a positive number. Then there exist natural
    numbers m, r such that 0 < or = r < q and n=mq+r

    Show that m and r exist and are also unique.

    **Fix q and induct on n, and note that you can only use rules of addition

    © BrainMass Inc. brainmass.com October 10, 2019, 4:15 am ad1c9bdddf

    Solution Preview

    Since q is a positive number, then q>=1.
    If q = 1, then for any natural number n, we must have n = n*1 = nq. Let m = n, r = 0, then m, q are natural numbers and n = mq + r.
    Now we consider q>=2 and make induction on n.
    If n = 0, then we can set m = 0, r = 0 and we ...

    Solution Summary

    The expert examines Euclidean Algorithm.