Last updated at October 28, 2026 by Teachoo
Transcript
Question 1 (ii) Compute the following using the improved version of Euclidβs algorithm. (ii) gcd(51000, 81000) Larger number should be first. So, we write gcd(51000, 81000) = gcd(81000, 51000) Finding remainder after doing (πππππ)/(πππππ) 1 51000 / 81000 51000 30000 Since remainder is 30000 Thus, gcd(81000, 51000) = gcd(51000, 30000) Again, finding remainder after doing (πππππ)/(πππππ) Since remainder is 21000 Thus, gcd(51000, 30000) = gcd(30000, 21000) Again, finding remainder after doing (πππππ)/(πππππ) 1 30000 / 51000 30000 21000 Again, finding remainder after doing (πππππ)/(πππππ) Since remainder is 9000 Thus, gcd(30000, 21000) = gcd(21000, 9000) Again, finding remainder after doing (πππππ)/(ππππ) 1 21000 / 30000 21000 9000 Since remainder is 3000 Thus, gcd(21000, 9000) = gcd(9000, 3000) Again, finding remainder after doing (ππππ)/(ππππ) 2 9000 / 21000 18000 3000 3 3000 / 9000 9000 0 Since remainder is 0 So, gcd (9000, 3000) = gcd (3000, 0) And, since one number is 0 gcd (3000, 0) = 3000 Thus, gcd(81000, 51000) = 3000