Results 1 to 3 of 3

Math Help - Extended Euclids Algorithm

  1. #1
    Junior Member
    Joined
    Jul 2012
    From
    Manchester
    Posts
    30

    Extended Euclids Algorithm

    a) Using the Euclideanalgorithm find the highest common factor of 1905623 and2766853. Findalso two integers h and k such that 1905623h + 2766853k = the HCFyou have found.


    Ive done the first part, but im not sure how the extended euclids algorithm works for the secound part
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Extended Euclids Algorithm

    Search the web for extended Euclidean algorithm, probably starting with Wikipedia. For efficient calculations, see this post and the entire thread.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,237
    Thanks
    1795

    Re: Extended Euclids Algorithm

    It's pretty straight forward, if you have done the first part.
    1905623 divides into 2766853 once with remainder 861230: 2766853- 1905623= 861230. 861230 divides into 1905623 twice with remainder 183163: 1905623- 2(61230)= 18163. 18163 divides into 861230 47 times with remainder 7569: 861230- 47(18163)= 7569. 7569 divides into 18163 twice with remainder 3025: 18163- 2(7569)= 3025. 3025 divides into 7569 twice with remainder 1519: 7569- 2(3025)= 1519. 1519 divides into 3025 once with remainder 1506: 3025- 1519= 1506. 1506 divides into 1519 once with remainder 13: 1519- 1505= 13. 13 divides into 1506 115 times with remainder 11: 1506- 115(13)= 11. 11 divides into 13 once with remainder 2: 13- 11= 2. Finally, 2 divides into 11 5 times with remainder 1: 11- 5(2)= 1. That tells us that 1905623 and 2766853 are "relatively prime"- their greatest common factor is 1.

    Now work backwards. Replace the "2" in 11- 5(2)= 1 with 13- 11 from the previous equation: 11- 5(2)= 11- 5(13- 11)= 6(11)- 5(13)= 1. Replace the "11" in the equation with 1506- 115(13) from the equation before that: 6(11)- 5(13)= 6(1506- 115(13))- 5(13)= 6(1506)- 690(13)- 5(13)= 6(1506)- 695(13)= 1. Replace the "13" in that equation with 1519- 1505= 13. Continue like that until the left side has the original two numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclids Algorithm and Multiple Inverses
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 13th 2012, 02:03 AM
  2. Extended Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2011, 08:27 AM
  3. GCD and extended euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: December 11th 2010, 06:25 AM
  4. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 17th 2010, 11:10 PM
  5. GCD and the extended algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 9th 2007, 02:36 AM

Search Tags


/mathhelpforum @mathhelpforum