(iv) Compute gcd(2587392, 157656) using improved Euclid’s algorithm - End-of-Chapter Exercises

part 2 - Question 1 (iv) - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Question 1 (iv) - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Question 1 (iv) - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 5 - Question 1 (iv) - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 6 - Question 1 (iv) - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 7 - Question 1 (iv) - End-of-Chapter Exercises - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo Β· Class 9 Explore Class 9

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

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.