# Extended Euclids Algorithm

• Jul 21st 2012, 01:24 AM
Magical
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
• Jul 21st 2012, 03:06 AM
emakarov
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.
• Jul 21st 2012, 07:16 AM
HallsofIvy
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.