Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Finding GCD using Euclid's algorithm

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    17

    Question Finding GCD using Euclid's algorithm

    I am having trouble with this problem. I can work the problem to find the GCD but I cannot get it to work backwarks so that I can express it in
    ma + nb form. Can anyone help me. The problem is for (116, -84)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by helpinmath View Post
    I am having trouble with this problem. I can work the problem to find the GCD but I cannot get it to work backwarks so that I can express it in
    ma + nb form. Can anyone help me. The problem is for (116, -84)
    Using the algorithm:

    (116, -84) = (116, 84) = (32, 84) = (32, 20) = (12, 20) = (12, 8) = (4, 8) = (4, 4) = 4.

    Working backwards:

    4 = 8 - 4 = 8 - (12 - 8) = 2*8 - 12 = 2*(20 - 12) - 12 = 2*20 - 3*12 = 2*20 - 3*(32 - 20) = 5*20 - 3*32 = 5*(84 - 2*32) - 3*32 = 5*84 - 13*32 = 5*84 - 13*(116 - 84) = 18*84 - 13*116 = -18*(-84) - 13*116
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2008
    Posts
    17
    I can see the substitution, but where did the 5*comes from?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by helpinmath View Post
    I can see the substitution, but where did the 5*comes from?
    5*... shows up in several places. be specific as to what you are talking about
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2008
    Posts
    17
    I guess I am just not getting it. I see the parenthesis is the substitution from the upper part. But throughout the problem there is multiplication and I do not know where those numbers are coming from. I am taking this class as a distant education with no help at all.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2008
    Posts
    17
    2*(20 - 12) like here for instance, how did you get the two?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2008
    Posts
    17

    Euclid's algorithm

    Here is another problem that I think I may have gotten,

    (85,65)

    5=3*85 + -4*65

    Hope this is right!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by helpinmath View Post
    I guess I am just not getting it. I see the parenthesis is the substitution from the upper part. But throughout the problem there is multiplication and I do not know where those numbers are coming from. I am taking this class as a distant education with no help at all.
    if finding the linear combination for the gcd is your objective as much as finding the gcd is, then i suggest using the matrix form of the Euclidean algorithm. have you ever heard of this? seen it?

    anyway, as iceman said, you find the combination by working backwards.

    now, obviously what you have is wrong, just work it out, 3*85 + (-4)65 = -5 not 5. it should be (-3)(85) + 4(65) perhaps. lets check

    run the algorithm on (85,65)

    85 = 1*65 + 20 ......................(1)
    65 = 3*20 + 5 ........................(2)
    20 = 4*5 + 0 ..........................(3)

    so that 5 is the gcd(85,65)

    Now to find the linear combination, start at line (2). (it will always be the case that you start at the second to last line)

    we have 65 = 3*20 + 5

    => 5 = 65 - 3*20

    now, we want to keep the 65, but we don't want the 20, we want a linear combination of 65 and 85, so change 20 based on line (1)

    => 5 = 65 - 3(85 - 1*65)
    => 5 = 65 - 3*85 + 3*65
    => 5 = 4*65 + (-3)*85

    and there's our linear combination. you apply the same concept to longer algorithms. just repeatedly change out numbers you don't want based on the previous line they appear in.


    now lets see how the matrix method works. you basically apply the same algorithm, but keep track of remainders in a matrix

    So, we want to find (85,65), so we set up a matrix in the following way. treat (85,65) as (x,y) and we will set up an augmented matrix based on the system:

    1*85 + 0*65 = 85
    0*85 + 1*65 = 65

    so 85 is your x and 65 is your y. now if you were to solve this system using matrices (or, in a weird way, unsolve it, since this is already in reduced row-echelon form), you would do the following

    \left( \begin{array}{ccc} 1 & 0 & 85 \\ 0 & 1 & 65 \end{array} \right) \begin{array}{l} \text{...R1} \\ \text{...R2} \end{array}
    ------------------------------
    \left( \begin{array}{ccc} 0 & 1 & 65 \\ 1 & -1 & 20 \end{array} \right) \begin{array}{l} \text{...R2} \\ \text{...R1 - R2} \end{array}
    ------------------------------
    \left( \begin{array}{ccc} 1 & -1 & 20 \\ -3 & 4 & 5 \end{array} \right) \begin{array}{l} \text{...R2} \\ \text{...R1 - 3*R2} \end{array}
    ------------------------------
    \left( \begin{array}{ccc} -3 & 4 & 5 \\ 13 & -17 & 0 \end{array} \right) \begin{array}{l} \text{...R2} \\ \text{...R1 - 4*R2 ...we get 0 here, so we stop the algorithm} \end{array}

    now, remember, the first column represents our x value, which is 85, and the second represents our y value, which is 65. so the first row of the last matrix says: -3*x + 4*y = -3*85 + 4*65 = 5

    and there is our combination. so in one swoop, we find the linear combination and the gcd
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2008
    Posts
    17

    Cool

    Thanks for the breakdown of that problem. I have tried to use it to do another one but I get stuck half way down using the matrix. Here is what I have so far...

    (116, -84)


    1 0 116
    0 1 84
    0 1 84
    1 -1 32
    1 -1 32
    -2 3 20 Here is where I get stuck. The number seems to get higher instead of lower.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Sep 2008
    Posts
    17

    Another Problem using matrix

    (72, 26) Using matrix algorithm

    I am still getting stuck down in the middle.

    1 0 72
    0 1 26
    0 1 26
    1 -1 46
    1 -1 46 Here is where I get stuck.




    And another:

    (72,25)

    1 0 72
    0 1 25
    0 1 25
    1 -1 47
    1 -1 47
    -2 3 -69 I do not think this is right.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    For the first problem, remember to keep subtracting x until you get a number less than x.

    1; 0; 72
    0; 1; 26

    changes to

    0; 1; 26
    1; -2; 20

    continuing...

    1; -2; 20
    -1; 3; 6
    ----------
    -1; 3; 6
    4; -11; 2
    ----------
    4; -11; 2
    -13; 36; 0

    Hence 4*72 - 11*26 = 2

    and the GCD is 2.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Mel
    Mel is offline
    Junior Member
    Joined
    Sep 2008
    Posts
    36

    Wink I hope this is right for (72, 25)

    I hope this is right for (72, 25)

    1 0 72
    0 1 25
    0 1 25
    1 -2 22
    1 -2 22
    -1 3 3
    -1 3 3
    0 1 0
    Follow Math Help Forum on Facebook and Google+

  13. #13
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Mel View Post
    I hope this is right for (72, 25)

    1 0 72
    0 1 25
    0 1 25
    1 -2 22
    1 -2 22
    -1 3 3
    -1 3 3
    0 1 0
    actually it's not. and it's not that hard to see. the first thing that should scream it out to you is that you end up with a line that says 0 1 0. and we know this can't be right, since you began with 0 1 25. you can't have a number equaling zero and 25 at the same time. secondly, according to this, the gcd is 3. this is of course absurd, as 3 does not divide 25
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Sep 2008
    Posts
    17
    Thanks for you wonderful words of wisdom. I am trying though to do this on my own, I am not just looking for answers. Sorry!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by helpinmath View Post
    Thanks for you wonderful words of wisdom. I am trying though to do this on my own, I am not just looking for answers. Sorry!
    so you like the matrix method, huh?

    your professor won't have a problem with you doing it this way, will he/she?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2012, 11:32 AM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum