Results 1 to 3 of 3

Math Help - GCD and the extended algorithm

  1. #1
    Member
    Joined
    Aug 2007
    Posts
    96

    GCD and the extended algorithm

    find the gcd of (713, 552) (which is (a,b))and then find s,t such that d = sa + tb

    i found the gcd to be 23, but i need help with the procedure for finding s and t
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Here's an interesting method, I don't know if it's standard. It's from Elementary Number Theory - Clark. I'll try to upload some examples of it in action later if I have time.
    Attached Thumbnails Attached Thumbnails GCD and the extended algorithm-blanki.jpg  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member DivideBy0's Avatar
    Joined
    Mar 2007
    From
    Melbourne, Australia
    Posts
    432
    Here is an example

    Attached Thumbnails Attached Thumbnails GCD and the extended algorithm-img1.jpg   GCD and the extended algorithm-img2.jpg   GCD and the extended algorithm-img3.jpg  
    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, 07:27 AM
  2. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: December 11th 2010, 05:25 AM
  3. Extended Euclid's algorithm - multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 12th 2010, 01:45 AM
  4. Extended Euclidean algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 21st 2009, 01:24 PM
  5. Replies: 6
    Last Post: March 31st 2009, 05:44 PM

Search Tags


/mathhelpforum @mathhelpforum