Results 1 to 10 of 10

Math Help - Euclidean algorithm

  1. #1
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Euclidean algorithm

    Determine with Euclid's algorithm. State also the first two residues and if we start with .


    (SGD means GCD)
    i need the answer fast if any1 can plz i have solve it this far:
    14400=14*1022+92 (r1=92)
    1022=92*11+10 (r2=10)
    92=9*10+2


    backwards
    2=9*10-92
    10=92*11-1022
    92=14*1022-14400

    i cant finish this plz any1?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Euclidean algorithm

    What does the question ask that you have not answered?

    See also an applet performing Euclid's algorithm here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    the qeustion is GCD(14400,1022)=?
    the answe is 2 but i really did not get it how they did get it, did i calculate wrong?
    if im honest i havent really understand this Euclidean algorithm
    Last edited by Petrus; September 25th 2012 at 11:54 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Euclidean algorithm

    you've almost finished. you found gcd(14400,1022) = 2 correctly.

    now you just need to express 2 as an integral linear combination of 1022 and 14400.

    2 = 92 - (9)(10) (we have 2 as a comb. of 10 and 92. we need to dig deeper. by the way, you had this BACKWARDS).

    10 = 1022 - (92)(11)(something with 1022 in it! good, we need that! you also had this BACKWARDS, which would have led to the wrong SIGN).

    so 2 = 92 - (9)(1022 - (92)(11)) = 92 - (9)(1022) + (99)(92) = (100)(92) - (9)(1022) (now we have 2 as a comb. of 92 and 1022. if only we had 92 as a comb. of 1022 and 14400. oh wait! we do!!!)

    92 = 14400 - (14)(1022) (so NOW, we can replace all the 92's in our expression for 2 with 14400 - (14)(1022)). so:

    2 = (100)(14400 - (14)(1022)) - (9)(1022) = (100)(14400) - (1400)(1022) - (9)(1022) = (100)(14400) - (1409)(1022).

    can this really be true? it's easy enough to check:

    (100)(14400) = 1440000
    (1409)(1022) = 1439998

    yep, the difference is 2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    omgg now i get it so always the last one u backwards is the answer of the question :P?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778

    Re: Euclidean algorithm

    Quote Originally Posted by Petrus View Post
    the answe is 2 but i really did not get it how they did get it
    The result of the Euclid's algorithm is the last nonzero remainder. In your case, the next line after 92 = 9 * 10 + 2 would be 10 = 5 * 2 + 0 with zero remainder.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    yeah thats what i mean ty alot emakarov! i really had a problem to understand this untill u did reply! ty alot!!!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,391
    Thanks
    758

    Re: Euclidean algorithm

    i will try to explain the LOGIC behind the euclidean algorithm. to do this, it's easier to work with smaller numbers.

    ok, let's say we want to find gcd(14,90).

    the first step is to divide 90 by 14, and "keep the quotient and remainder".

    90 = (6)(14) + 6

    now if something (call it d for now) divides 90 AND 14, then it surely also divides 6 = 90 - (6)(14), so we're looking for a number smaller than 6 (which is a LOT easier than looking for a number smaller than 14).

    [EDIT: let me amplify this:

    d|90 and d|14 means:

    90 = md
    14 = nd, for some positive integers m and n.

    so 6 = 90 - (6)(14) = md - 6(nd) = (m - 6n)d. this shows that d also divides the DIFFERENCE of 90 and 84 = (6)(14). in this particular example, it turns out that d = 2, which means that m = 45, and n = 7.

    indeed 2 divides 6 (90 - 84).

    it turns out that another way of defining gcd(a,b) is the SMALLEST positive integer out of ALL possible integer combinations ma+nb, which is in some ways "easier to use" than "factoring" (especially with LARGE integers). this algorithm gives you a way to actually find m and n. ]

    what we've done here, is established that gcd(90,14) = gcd(90-84,14) = gcd(6,14). so now we're looking for gcd(6,14). so we divide 14 by 6 (and keep the quotient and remainder, as before):

    14 = (2)(6) + 2

    again, if something divides 14, and it divides 6, it must surely also divide 14 - (2)(6) = 2. so now we're looking for gcd(2,6), which is even easier.

    ok, so we divide 6 by 2:

    6 = (3)(2) + 0 <--remainder of 0!!! yay!!! 2 divides 6 evenly. now, we stop, and "back up one step".

    since 2 divides 6, gcd(2,6) = 2 (nothing smaller than 2 will ever divide 2, right?). so, "the next-to-last remainder" we get (before we got a remainder of 0) is our gcd.

    so, to re-cap:

    gcd(14,90) = gcd(6,14) = gcd(2,6) = 2.

    check by factoring:

    90 = 2*45 = 2*5*9 = 2*3*3*5
    14 = 2*7

    indeed, the only common factor is 2.

    the "key step" in all of this is this simple one:

    suppose b > a. then gcd(a,b) = gcd(a,a-b). if fact, if ka < b, then gcd(a,b) = gcd(a,b-ka).

    so if we choose k to make b-ka as small as possible (hint: "divide"), by using b = qa + r, where r < a, then we turn a "hard problem" like finding gcd(a,b) into the "easier one" of finding gcd(r,a) = gcd(a,r) = gcd(a,r+qa) = gcd(a,b) (remember r = b - qa, so here our "k" is "q", the quotient, and we already KNOW that:

    gcd(a,b) = gcd(a,b-qa) as long as qa < b).
    Last edited by Deveno; September 25th 2012 at 12:31 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    11,697
    Thanks
    452

    Re: Euclidean algorithm

    please post number theory problems in the correct forum.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Sep 2012
    From
    Sweden
    Posts
    250
    Thanks
    6

    Re: Euclidean algorithm

    Quote Originally Posted by skeeter View Post
    please post number theory problems in the correct forum.
    Sorry im just bad on that:P well im studdy algebra so i guess evrything fr.o.m. My algebra book can be poster here sorry
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 5th 2011, 05:59 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 06:53 AM
  3. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 13th 2010, 07:25 PM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  5. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum