Last updated at October 28, 2026 by Teachoo
Transcript
Question 1 (iii) Compute the following using the improved version of Euclidβs algorithm. (iii) gcd(1789287, 237656) Larger number should be first, which is the case here Finding remainder after doing (πππππππ)/(ππππππ) 7 237656 \/ 1789287 1663592 125695 Since remainder is 125695 Thus, gcd(1789287, 237656) = gcd(237656, 125695) Again, finding remainder after doing (ππππππ)/(ππππππ) Since remainder is 111961 Thus, gcd(237656, 125695) = gcd(125695, 111961) Again, finding remainder after doing (πππππ)/(πππππ) 1 125695 / 237656 125695 111961 Again, finding remainder after doing (ππππππ)/(ππππππ) Since remainder is 13734 Thus, gcd(125695, 111961) = gcd(111961, 13734) Again, finding remainder after doing (ππππππ)/(πππππ) 1 111961 ,/ 125695 111961 13734 Since remainder is 2089 Thus, gcd(111961, 13734) = gcd(13734, 2089) Again, finding remainder after doing (πππππ)/(ππππ) 8 13734 / 111961 109872 2089 6 2089 \/ 13734 12534 1200 Since remainder is 1200 Thus, gcd(13734, 2089) = gcd(2089, 1200) Again, finding remainder after doing (ππππ)/(ππππ) Since remainder is 889 Thus, gcd(2089, 1200) = gcd(1200, 889) Again, finding remainder after doing (πππππ)/(πππππ) 1 1200 / 2089 1200 889 Again, finding remainder after doing (ππππ)/(πππ) Since remainder is 311 Thus, gcd(1200, 889) = gcd(889, 311) Again, finding remainder after doing (πππ)/(πππ) 1 889 /1200 889 311 Since remainder is 267 Thus, gcd(889, 311) = gcd(311, 267) Again, finding remainder after doing (πππ)/(πππ) 2 311 / 889 622 267 1 267 / 311 44 Since remainder is 44 Thus, gcd(311, 267) = gcd(267, 44) Again, finding remainder after doing (πππ)/(ππ) Since remainder is 3 Thus, gcd(267, 44) = gcd(44, 3) Again, finding remainder after doing (πππ)/(ππ) 44 / 267 264 Again, finding remainder after doing (ππ)/(π) Since remainder is 2 Thus, gcd(44, 3) = gcd(3, 2) Again, finding remainder after doing (π)/(π) 14 3/44 12 Since remainder is 1 Thus, gcd(3, 2) = gcd(2, 1) Again, finding remainder after doing (π)/(π) Since remainder is 0 So, gcd (2, 1) = gcd (1, 0) And, since one number is 0 gcd (1, 0) = 1 Thus, gcd(1789287, 237656) = 1