Printable View
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
Search the web for extended Euclidean algorithm, probably starting with Wikipedia. For efficient calculations, see this post and the entire thread.
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.