Scanning numbers from n down to 1 populates the divisor list in descending order rather than ascending order. Because the largest divisors are added first, the list of common divisors between two numbers will also be ordered from greatest to least. To report the greatest common divisor at the end, tRead more
Scanning numbers from n down to 1 populates the divisor list in descending order rather than ascending order. Because the largest divisors are added first, the list of common divisors between two numbers will also be ordered from greatest to least. To report the greatest common divisor at the end, the algorithm must select the first, leftmost element rather than the rightmost.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
Working backwards from min(m, n) down to 1 allows the algorithm to stop early. The very first number encountered that divides both m and n is guaranteed to be the largest common factor. We can immediately report this number as the GCD and terminate the process, completely eliminating the need to exaRead more
Working backwards from min(m, n) down to 1 allows the algorithm to stop early. The very first number encountered that divides both m and n is guaranteed to be the largest common factor. We can immediately report this number as the GCD and terminate the process, completely eliminating the need to examine the remaining numbers all the way down to 1.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
Apply the division algorithm starting with the larger number: divide 825 by 375, which leaves a quotient of 2 and remainder 75, reducing the problem to gcd(375, 75). Next, divide 375 by 75, giving a quotient of 5 and remainder 0, reducing to gcd(75, 0). Because the second number is now 0, the algoriRead more
Apply the division algorithm starting with the larger number: divide 825 by 375, which leaves a quotient of 2 and remainder 75, reducing the problem to gcd(375, 75). Next, divide 375 by 75, giving a quotient of 5 and remainder 0, reducing to gcd(75, 0). Because the second number is now 0, the algorithm halts and reports gcd(375, 825) = 75.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
Successively take remainders: 1789287 mod 237656 = 125695; 237656 mod 125695 = 111961; 125695 mod 111961 = 13734; 111961 mod 13734 = 2089; 13734 mod 2089 = 1200; 2089 mod 1200 = 889; 1200 mod 889 = 311; 889 mod 311 = 267; 311 mod 267 = 44; 267 mod 44 = 3; 44 mod 3 = 2; 3 mod 2 = 1; and 2 mod 1 = 0.Read more
Successively take remainders: 1789287 mod 237656 = 125695; 237656 mod 125695 = 111961; 125695 mod 111961 = 13734; 111961 mod 13734 = 2089; 13734 mod 2089 = 1200; 2089 mod 1200 = 889; 1200 mod 889 = 311; 889 mod 311 = 267; 311 mod 267 = 44; 267 mod 44 = 3; 44 mod 3 = 2; 3 mod 2 = 1; and 2 mod 1 = 0. Reaching remainder zero leaves gcd(1, 0) = 1.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?
Scanning numbers from n down to 1 populates the divisor list in descending order rather than ascending order. Because the largest divisors are added first, the list of common divisors between two numbers will also be ordered from greatest to least. To report the greatest common divisor at the end, tRead more
Scanning numbers from n down to 1 populates the divisor list in descending order rather than ascending order. Because the largest divisors are added first, the list of common divisors between two numbers will also be ordered from greatest to least. To report the greatest common divisor at the end, the algorithm must select the first, leftmost element rather than the rightmost.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
https://www.tiwariacademy.com/ncert-solutions/class-9/maths/ganita-manjari-chapter-11/
See lessWhat about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?
Working backwards from min(m, n) down to 1 allows the algorithm to stop early. The very first number encountered that divides both m and n is guaranteed to be the largest common factor. We can immediately report this number as the GCD and terminate the process, completely eliminating the need to exaRead more
Working backwards from min(m, n) down to 1 allows the algorithm to stop early. The very first number encountered that divides both m and n is guaranteed to be the largest common factor. We can immediately report this number as the GCD and terminate the process, completely eliminating the need to examine the remaining numbers all the way down to 1.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
https://www.tiwariacademy.com/ncert-solutions/class-9/maths/ganita-manjari-chapter-11/
See lessCompute gcd(375, 825) using the improved version of Euclid’s algorithm.
Apply the division algorithm starting with the larger number: divide 825 by 375, which leaves a quotient of 2 and remainder 75, reducing the problem to gcd(375, 75). Next, divide 375 by 75, giving a quotient of 5 and remainder 0, reducing to gcd(75, 0). Because the second number is now 0, the algoriRead more
Apply the division algorithm starting with the larger number: divide 825 by 375, which leaves a quotient of 2 and remainder 75, reducing the problem to gcd(375, 75). Next, divide 375 by 75, giving a quotient of 5 and remainder 0, reducing to gcd(75, 0). Because the second number is now 0, the algorithm halts and reports gcd(375, 825) = 75.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
https://www.tiwariacademy.com/ncert-solutions/class-9/maths/ganita-manjari-chapter-11/
See lessCompute gcd(51000, 81000) using the improved version of Euclid’s algorithm.
Divide 81000 by 51000 to get remainder 30000, reducing to gcd(51000, 30000). Then 51000 = 1 × 30000 + 21000, leaving gcd(30000, 21000). Next, 30000 = 1 × 21000 + 9000, leaving gcd(21000, 9000). Then 21000 = 2 × 9000 + 3000, leaving gcd(9000, 3000). Finally, 9000 = 3 × 3000 + 0, leaving gcd(3000, 0).Read more
Divide 81000 by 51000 to get remainder 30000, reducing to gcd(51000, 30000). Then 51000 = 1 × 30000 + 21000, leaving gcd(30000, 21000). Next, 30000 = 1 × 21000 + 9000, leaving gcd(21000, 9000). Then 21000 = 2 × 9000 + 3000, leaving gcd(9000, 3000). Finally, 9000 = 3 × 3000 + 0, leaving gcd(3000, 0). Thus, the greatest common divisor is 3000.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
https://www.tiwariacademy.com/ncert-solutions/class-9/maths/ganita-manjari-chapter-11/
See lessCompute gcd(1789287, 237656) using the improved version of Euclid’s algorithm.
Successively take remainders: 1789287 mod 237656 = 125695; 237656 mod 125695 = 111961; 125695 mod 111961 = 13734; 111961 mod 13734 = 2089; 13734 mod 2089 = 1200; 2089 mod 1200 = 889; 1200 mod 889 = 311; 889 mod 311 = 267; 311 mod 267 = 44; 267 mod 44 = 3; 44 mod 3 = 2; 3 mod 2 = 1; and 2 mod 1 = 0.Read more
Successively take remainders: 1789287 mod 237656 = 125695; 237656 mod 125695 = 111961; 125695 mod 111961 = 13734; 111961 mod 13734 = 2089; 13734 mod 2089 = 1200; 2089 mod 1200 = 889; 1200 mod 889 = 311; 889 mod 311 = 267; 311 mod 267 = 44; 267 mod 44 = 3; 44 mod 3 = 2; 3 mod 2 = 1; and 2 mod 1 = 0. Reaching remainder zero leaves gcd(1, 0) = 1.
For more NCERT Solutions of Class 9 Maths Ganita Manjari Part 2 Chapter 11 The World of Algorithms Question Answer (2026-27)
https://www.tiwariacademy.com/ncert-solutions/class-9/maths/ganita-manjari-chapter-11/
See less