Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Eucprf

    Uploaded by

    Md Sahin Siraj
    1) The document proves that the Euclidean algorithm correctly computes the greatest common divisor (GCD) of two integers a and b. 2) It does this by using mathematical induction to show that at each step of the algorithm, the GCD is equal to the GCD of the current remainders. 3) Since the remainders monotonically decrease at each step until one is 0, the last nonzero remainder rn must equal the GCD of the original numbers a and b.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Eucprf

    Uploaded by

    Md Sahin Siraj
    13 views2 pages
    1) The document proves that the Euclidean algorithm correctly computes the greatest common divisor (GCD) of two integers a and b. 2) It does this by using mathematical induction to show that at each step of the algorithm, the GCD is equal to the GCD of the current remainders. 3) Since the remainders monotonically decrease at each step until one is 0, the last nonzero remainder rn must equal the GCD of the original numbers a and b.

    Original Description:

    Euclidean proof

    Original Title

    eucprf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1) The document proves that the Euclidean algorithm correctly computes the greatest common divisor (GCD) of two integers a and b. 2) It does this by using mathematical induction to show that at each step of the algorithm, the GCD is equal to the GCD of the current remainders. 3) Since the remainders monotonically decrease at each step until one is 0, the last nonzero remainder rn must equal the GCD of the original numbers a and b.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    13 views2 pages

    Eucprf

    Uploaded by

    Md Sahin Siraj
    1) The document proves that the Euclidean algorithm correctly computes the greatest common divisor (GCD) of two integers a and b. 2) It does this by using mathematical induction to show that at each step of the algorithm, the GCD is equal to the GCD of the current remainders. 3) Since the remainders monotonically decrease at each step until one is 0, the last nonzero remainder rn must equal the GCD of the original numbers a and b.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Proof that the Euclidean Algorithm Works

    Recall this definition: When a and b are integers and a 6= 0 we say a divides
    b, and write a|b, if b/a is an integer.
    1. Use the definition to prove that if a, b, c, x and y are integers and a|b
    and a|c, then a|(bx + cy).
    Answer: We are given that the two quotients b/a and c/a are integers.
    Therefore the integer linear combination (b/a) × x + (c/a) × y = (bx + cy)/a is
    an integer, which means that a|(bx + cy).
    2. Use Question 1 to prove that if a is a positive integer and b, q and r are
    integers with b = aq + r, then gcd(b, a) = gcd(a, r).
    Answer: Write m = gcd(b, a) and n = gcd(a, r). Since m divides both b and
    a, it must also divide r = b − aq by Question 1. This shows that m is a common
    divisor of a and r, so it must be ≤ n, their greatest common divisor. Likewise,
    since n divides both a and r, it must divide b = aq + r by Question 1, so n ≤ m.
    Since m ≤ n and n ≤ m, we have m = n.
    Alternative answer: Let c be a common divisor of b and a. Then by Question
    1, c must divide r = b − aq. Thus, the set D of common divisors of b and a is
    a subset of the set E of common divisors of a and r. Now let d be a common
    divisor of a and r. Then by Question 1, d must divide b = aq + r. Thus, the set
    E of common divisors of a and r is a subset of the set D of common divisors of
    b and a. Hence D = E and the largest integer in this set is both gcd(b, a) and
    gcd(a, r). Therefore gcd(b, a) = gcd(a, r).

    1
    Recall the Euclidean algorithm:
    Let r0 = a and r1 = b be integers with a > b > 0. Apply the division
    algorithm x = yq + r, 0 ≤ r < y iteratively to obtain

    ri = ri+1 qi+1 + ri+2 with 0 < ri+2 < ri+1

    for 0 ≤ i < n − 1 and rn+1 = 0.


    3. Prove that gcd(a, b) = rn , the last nonzero remainder. Hint: First show
    that the algorithm terminates. Then use mathematical induction and Question
    2.
    Answer: First we show that the algorithm terminates. Since ri+2 < ri+1 ,
    we have r0 > r1 > r2 > · · · > rn > rn+1 = 0. This shows that the remainders
    are monotonically strictly decreasing positive integers until the last one, which
    is rn+1 = 0. Therefore the algorithm stops after no more than b divisions.
    We prove by induction the claim that for each i in 0 ≤ i ≤ n we have
    gcd(a, b) = gcd(ri , ri+1 ).
    For the base step i = 0, we have gcd(a, b) = gcd(r0 , r1 ) by definition of
    r0 = a and r1 = b.
    For each i in 0 ≤ i < n we have gcd(ri , ri+1 ) = gcd(ri+1 , ri+2 ) by Question
    2. This shows that if gcd(a, b) = gcd(ri , ri+1 ), then gcd(a, b) = gcd(ri+1 , ri+2 ),
    which is the induction step. This ends the proof of the claim.
    Now use the claim with i = n: gcd(a, b) = gcd(rn , rn+1 ). But rn+1 = 0 and
    rn is a positive integer by the way the Euclidean algorithm terminates. Every
    positive integer divides 0. If rn is a positive integer, then the greatest common
    divisor of rn and 0 is rn . Thus, the Euclidean algorithm correctly computes the
    greatest common divisor of its input a and b as gcd(a, b) = rn .

    You might also like