Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By tonio
  • 1 Post By tonio

Math Help - Greastest Common Divisor

  1. #1
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093

    Greastest Common Divisor

    there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

    ax+by = d

    My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

    I tried to solve it many times but always I fail, please help.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2009
    Posts
    13
    Can you give a specific example?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    9
    Quote Originally Posted by Amer View Post
    there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

    ax+by = d

    My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

    I tried to solve it many times but always I fail, please help.

    Thanks
    If you use Euclidean Algorithm, then you have to do messy backsubstitution steps. It is more direct to use the Extended Euclidean Algorithm, see Extended Euclidean algorithm - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Amer View Post
    there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

    ax+by = d

    My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

    I tried to solve it many times but always I fail, please help.

    Thanks

    You have to express backwards each residue r_n as a combination of the previous residue r_(n-1) and the quotient q_n.

    Example: a = 120, b = 23. We begin the Euclidean algorithm

    ### 120 = 5*23 + 5 ==> q_1 = 23, r_1 = 5

    ### 23 = 4*5 + 3 ==> q_2 = 5 = r_1, r_2 = 3

    ### 5 = 1*3 + 2 ==> q_3 = 3 = r_2 , r_3 = 2

    ### 3 = 1*2 + 1 ==> q_4 = 2 = r_3 , r_4 = 1

    2 = 2*1 ===> q_5 = 2 = r_4, r_5 = 0 ==> the last non-zero residue, namely 1, is the gcd of 120 and 23

    Now we go backwards (begin with the one before the last row):

    (i) 1 = 3 - 1*2 ==> last non zero residue (i.e., the gcd) r_4 expressed as lin. comb. of quotient q_4 and prior residue r_3

    (ii) 2 = 5 - 1*3 ==> residue r_3 as l.c. of quotient q_3 and residue r_2, and now we plug into (i) and get: 1 = 3 - 1*(5 - 1*3) = 2*3 - 5

    (iii) 3 = 23 - 4*5 ==> residue r_2 as l.c. of q_2 and r_1, plug in (ii) above:

    1 = 2*(23 - 4*5) - 5 = 2*23 - 9*5

    (iv) 5 = 120 - 5*23 ==> residue r_1 as l.c. of q_1 and r_0 = 23.
    Plug into (iii) above and finally get:

    1 = 2*23 - 9*(120 - 5*23) = 47*23 +(-9)*120 and voilá.

    Tonio
    Thanks from Amer
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by tonio View Post
    You have to express backwards each residue r_n as a combination of the previous residue r_(n-1) and the quotient q_n.

    Example: a = 120, b = 23. We begin the Euclidean algorithm

    ### 120 = 5*23 + 5 ==> q_1 = 23, r_1 = 5

    ### 23 = 4*5 + 3 ==> q_2 = 5 = r_1, r_2 = 3

    ### 5 = 1*3 + 2 ==> q_3 = 3 = r_2 , r_3 = 2

    ### 3 = 1*2 + 1 ==> q_4 = 2 = r_3 , r_4 = 1

    2 = 2*1 ===> q_5 = 2 = r_4, r_5 = 0 ==> the last non-zero residue, namely 1, is the gcd of 120 and 23

    Now we go backwards (begin with the one before the last row):

    (i) 1 = 3 - 1*2 ==> last non zero residue (i.e., the gcd) r_4 expressed as lin. comb. of quotient q_4 and prior residue r_3

    (ii) 2 = 5 - 1*3 ==> residue r_3 as l.c. of quotient q_3 and residue r_2, and now we plug into (i) and get: 1 = 3 - 1*(5 - 1*3) = 2*3 - 5

    (iii) 3 = 23 - 4*5 ==> residue r_2 as l.c. of q_2 and r_1, plug in (ii) above:

    1 = 2*(23 - 4*5) - 5 = 2*23 - 9*5

    (iv) 5 = 120 - 5*23 ==> residue r_1 as l.c. of q_1 and r_0 = 23.
    Plug into (iii) above and finally get:

    1 = 2*23 - 9*(120 - 5*23) = 47*23 +(-9)*120 and voilá.

    Tonio
    I know all that but what I want is the proof of this theorem not example, anyway thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Amer View Post
    I know all that but what I want is the proof of this theorem not example, anyway thanks

    This is what you wrote in your first messaage:

    "there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.



    My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

    I tried to solve it many times but always I fail, please help.

    Thanks "

    The above says nothing about proving anything, and you even tell us that you don't know how to do it.
    This is what I showed you: how to do it, by means of an example, because this is what you asked.
    The proof why it works is a straightforward, and pretty easy, induction on the number of steps required to reach the gcd. Since you "know all that" it must be crystal clear how to work out the induction

    Tonio
    Thanks from Amer
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 06:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  3. Common Divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 6th 2010, 12:05 PM
  4. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 01:36 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 08:16 PM

Search Tags


/mathhelpforum @mathhelpforum