Explore BrainMass
Share

Explore BrainMass

    Extended Euclidian Algorithm Proofs

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

    (See attached file for full problem description)

    ---
    Given positive integers a and b, the extended Euclidian algorithm constructs sequences qn, rn, sn and tn, which are defined recursively as follows:

    q0=0, q1=0, qn= q└ rn-2/ rn-1 ┘ for n>=2;
    r0=a, r1=b, rn= rn-2 - qnrn-1 for n>=2;
    s0=1, s1=0, sn= sn-2 - qnsn-1 for n>=2;
    t0=0, t1=1, tn= tn-2 - qntn-1 for n>=2;

    the sequences terminating if rn=0 . Prove the following

    i) The extended Euclidian algorithm always terminates, i.e., there exists n>=2 such that rn=0
    (hint : first show that if k>0 and rk>0 then 0<= rk+1<rk.)
    ii) If 0<=k<=n then ska+tkb = rk.
    iii) If 1<=k<=n then gcd(rk-1,rk) = gcd(a,b).
    iv) rn-1= sn-1a+tn-1b= gcd(a,b)
    ---

    © BrainMass Inc. brainmass.com October 9, 2019, 5:42 pm ad1c9bdddf
    https://brainmass.com/math/discrete-math/extended-euclidian-algorithm-proofs-65120

    Attachments

    Solution Preview

    Please see the attached file for the complete solution.
    Thanks for using BrainMass.

    Proof:
    a) For , we have , where means the greatest integer less than or equal to ...

    Solution Summary

    Extended Euclidian Algorithm Proofs are provided. The solution is detailed and well presented.

    $2.19