Results 1 to 3 of 3

Math Help - Extended Euclidean algorithm

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    2

    Extended Euclidean algorithm

    Find the greatest common divisor D of the integers A and B, and write D with ax + by.

    like in:

    a = 60 b = 100

    What i did to find the GCD:
    100/60=1 remain 40.
    60/40=1 remain 20.
    40/20=2 remain 0.

    GCD(60,100) = 20 that is the last remainder non-null.

    Continuing:

    40 = 100-1.60
    20 = 60-1.40

    But what do I do now?
    Thaks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by geisonmcd View Post
    Find the greatest common divisor D of the integers A and B, and write D with ax + by.

    like in:

    a = 60 b = 100

    What i did to find the GCD:
    100/60=1 remain 40.
    60/40=1 remain 20.
    40/20=2 remain 0.

    GCD(60,100) = 20 that is the last remainder non-null.

    Continuing:

    40 = 100-1.60
    20 = 60-1.40

    But what do I do now?
    Thaks in advance.
    Reduce both a & b by the gcd, making the revised GCD equal to 1.


    (a): \dfrac{60}{20} = 3

    (b): \dfrac{100}{20} = 5

    3x + 5y = 1
    3(2) + 5(-1) = 1

    x=2, y=-1

     ax + by = gcd(a,b)
     60 \cdot 2 + 100 \cdot -1 = 20
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    2

    Where

    Quote Originally Posted by aidan View Post
    Reduce both a & b by the gcd, making the revised GCD equal to 1.


    (a): \dfrac{60}{20} = 3

    (b): \dfrac{100}{20} = 5

    3x + 5y = 1
    3(2) + 5(-1) = 1


    x=2, y=-1

     ax + by = gcd(a,b)
     60 \cdot 2 + 100 \cdot -1 = 20
    Hey,I didn't get it. From where the 2 and -1 after you have wrote 3x+ 5y = 1 came from?
    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. Extended euclidean algorighm question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 4th 2009, 11:16 AM
  4. Replies: 6
    Last Post: March 31st 2009, 06:44 PM
  5. Extended Euclidean related polynomial's inverse
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: October 12th 2008, 01:59 PM

Search Tags


/mathhelpforum @mathhelpforum