Last updated at October 28, 2026 by Teachoo
Transcript
Question 1 (iv) Compute the following using the improved version of Euclidβs algorithm. (iv) gcd(2587392, 157656) Larger number should be first, which is the case here Finding remainder after doing (πππππππ)/(ππππππ) 16 157656 \/ 2587392 157656 1010832 945936 64896 Since remainder is 64896 Thus, gcd(2587392, 157656) = gcd(157656, 64896) Again, finding remainder after doing (ππππππ)/(πππππ) Since remainder is 27864 Thus, gcd(157656, 64896) = gcd(64896, 27864) Again, finding remainder after doing (πππππ)/(πππππ) 2 64896 / 157656 129792 27864 Again, finding remainder after doing (πππππ)/(πππππ) Since remainder is 9168 Thus, gcd(64896, 27864) = gcd(27864, 9168) Again, finding remainder after doing (πππππ)/(ππππ) 2 27864 \/ 64896 55728 9168 Since remainder is 360 Thus, gcd(27864, 9168) = gcd(9168, 360) Again, finding remainder after doing (ππππ)/(πππ) 3 9168 / 27864 27504 360 Since remainder is 168 Thus, gcd(9168, 360) = gcd(360, 168) Again, finding remainder after doing (πππ)/(πππ) 25 360 / 9168 720 1968 1800 168 Since remainder is 24 Thus, gcd(360, 168) = gcd(168, 24) Again, finding remainder after doing (πππ)/(ππ) 2 168 / 360 336 24 24,\/ 168 168 Since remainder is 0 So, gcd (168, 24) = gcd (24, 0) And, since one number is 0 gcd (24, 0) = 24 Thus, gcd(2587392, 157656) = 24