(iii) Compute gcd(1789287, 237656) using improved version of Euclid’s - End-of-Chapter Exercises

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

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

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

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

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

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

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

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

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

part 11 - Question 1 (iii) - 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 (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

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.