Results 1 to 3 of 3

Math Help - Greastest Common Divisor question

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Oregon
    Posts
    1

    Greastest Common Divisor question

    equation: 111s + 153t = GCD(s,t)

    Question Find s and t

    I know how to do the problem first go through find the gcd of 111 and 153:
    151 = 111 + 42
    111 = 42*2 + 27
    42 = 27 + 15
    15 = 12 + 3
    12 = 3*4 + 0

    then I have to go back through and solve
    42 = 153 - 111
    27 = 111 - 42*2
    .... etc

    But everytime I try and solve it I get an answer that doesn't work, can anyone help me?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2012
    From
    Hyrule
    Posts
    39
    Thanks
    10

    Re: Greastest Common Divisor question

    You can find one solution (s0,t0) using this : Extended Euclidean algorithm - Wikipedia, the free encyclopedia
    Then all the solutions are (s0+153k, t0+111k), k in Z.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,383
    Thanks
    750

    Re: Greastest Common Divisor question

    you have to keep careful track of signs when "working backwards".

    you have a step missing from your gcd calculation, as well:

    27 = 15 + 12

    you also wrote down 151 instead of 153 in your derivation....little things like that can trip you up.

    now we know that:

    3 = 15 - 12
    12 = 27 - 15
    15 = 42 - 27
    27 = 111 - (2)(42)
    42 = 153 - 111

    so, working backwards, we get:

    3 = 15 - 12 = (42 - 27) - (27 - 15) we want to keep the 42 and 27, and trade the 15 in for a combination of 42 and 27:

    3 = (42 - 27) - (27 - (42 - 27)) = 42 - 27 - 27 + 42 - 27 (see how you need to be careful with the minus signs?)

    3 = (2)(42) - (3)(27) (just to be sure we haven't make a mistake yet: (2)(42) = 84, and (3)(27) = 81, and 84 - 81 = 3. cool, we're good so far.)

    now we need to "trade up" and express 42 and 27 in terms of "bigger numbers".

    since 42 = 153 - 111, and 27 = 111 - (2)(42), we have:

    3 = 2(153 - 111) - (3)(111 - 2(42)) = (2)(153) - (2)(111) - (3)(111) + (6)(42), let's collect like terms again before we get confused:

    3 = (2)(153) - (5)(111) + (6)(42) <----we still need to express 42 in terms of 151 and 111.

    3 = (2)(153) - (5)(111) + (6)(151 - 111) = (2)(153) - (5)(111) + (6)(153) - (6)(111) now collect like terms again:

    3 = (8)(153) - (11)(111). so s = -11, and t = 8.

    (sanity check: (8)(153) = 1224, and (11)(111) = 1221, and 1224 - 1221 = 3).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A greatest common divisor question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 15th 2012, 01:16 PM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Common Divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 6th 2010, 11:05 AM
  4. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  5. Greastest Common Divisor
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 9th 2009, 01:24 AM

Search Tags


/mathhelpforum @mathhelpforum