Results 1 to 7 of 7

Math Help - Extended Euclidean Algorithm - need help understanding 1 step

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    93

    Extended Euclidean Algorithm - need help understanding 1 step


    This comes from my notes. At the bottom where it says: 2*(50 - 1*35) = 3*35 - 2*50,
    I am not figuring out 3 and the 2 come from in 3*35 - 2*50. I tried multiplying which gives me the 2*50 but the 3*35 I do not understand how they getting that.

    This is easier with an example:
    Solve 135x + 50y = gcd(135, 50)
    135 = 250 + 35
    50 = 135 + 15
    35 = 215 + 5
    15 = 35 + 0, so gcd(135, 50) = 5
    5 = 35 215
    15 = 50 135,
    so 5 = 35 2(50 135) = 335 250
    35 = 135 250,
    so 5 = 3(135 250) 250 = 3135 850 (x = 3, y = -8)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    5 = 35 2(50 135) = 335 250
    Is this the line you are talking about? There is a 35 in the left side so you get 3.35 on the right.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by clic-clac View Post
    Is this the line you are talking about? There is a 35 in the left side so you get 3.35 on the right.
    Yes that is the line I am talking about. This right here:

    335 250
    ^
    |
    |

    I just do not know where that 3 is coming from
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jan 2009
    Posts
    93
    In other words, how does this:

    5 = 35 2(50 135)

    equal this:

    335 250

    Thats the only thing I am not understanding
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    -2(50-1.35)=-2.50+2.35 Do you agree?
    Now if you add 35, you obtain what you want.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jan 2009
    Posts
    93
    Quote Originally Posted by clic-clac View Post
    -2(50-1.35)=-2.50+2.35 Do you agree?
    Now if you add 35, you obtain what you want.
    It is not adding up because I am not getting:

    335 – 250

    I have to have it in this form.

    (I can not get 1 single answer, as you see in the example from post 1)

    Because this:

    335 – 250

    becomes this:

    3(135 – 250) – 250


    which I know how to do.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jan 2009
    Posts
    93
    I just figured out how they got it.

    This is what I see:

    35 – 2(50 – 135) = 335 – 250
    35 -
    2(50) + 2(35)

    Clic-Clac, when you told me about the extra 35, I am looking at it like this:

    1(35) - 2(50) + 2(35)

    Since (35) are common, we add them, giving me:

    - 2(50) + 3(35)

    Thats what I needed to figure out.

    Thanks for your help Clic-Clac
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Extended Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2011, 08:27 AM
  2. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: December 11th 2010, 06:25 AM
  3. Problems understanding The Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 13th 2010, 10:12 PM
  4. Extended euclidean algorighm question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 4th 2009, 11:16 AM
  5. Extended Euclidean algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 21st 2009, 02:24 PM

Search Tags


/mathhelpforum @mathhelpforum