IGKO is TODAY!
Mock Test ₹150 View Schedule

Ganita Manjari · Class 9 · Part II · Chapter 11

Ganita Manjari Class 9 Maths Chapter 11 The World of Algorithms Exercise 11.3 Solutions

Two questions on what happens to the gcd algorithms when we scan downwards instead of upwards. Each answer shows the change needed and counts the checks.

Last updated 6 October 2026

  • 2Questions
  • 1Diagrams
  • Ch 11The World of Algorithms

How to answer every question

  1. Decide the order of the scan Up from the bottom, or down from the top?
  2. Find which end holds the answer The largest divisor is at the right of an increasing list and at the left of a decreasing one.
  3. Look for an early stop If the first hit is the answer, we can stop and save work.
  4. Test on 375 and 825 Check against gcd(375, 825) = 75.

Increasing list: smallest first, so the greatest value is the rightmost.

Decreasing list: greatest first, so the greatest value is the leftmost.

Scan: examining the candidates one after another.

Reversing the order

Chapter 11 Exercise 11.3 Question 1 Solution How would the original gcd algorithm change if we computed the divisors of n by examining the numbers from n down to 1, in reverse order?

Answer: report the leftmost, not the rightmost
Step 1 · The lists come out in decreasing order

The loop now runs "for each j from n down to 1". The first divisor found is n itself and the last is 1, so the list is decreasing.

NumberDivisors found in reverse order
18[18, 9, 6, 3, 2, 1]
375[375, 125, 75, 25, 15, 5, 3, 1]
825[825, 275, 165, 75, 55, 33, 25, 15, 11, 5, 3, 1]
Step 2 · The common divisors are also in decreasing orderStep 5 must change

Going through divisors-of-m in order and keeping those that are also in divisors-of-n, we get the common divisors of 375 and 825 as [75, 25, 15, 5, 3, 1].

The original last step reports the rightmost element. Now that is 1, which is wrong, because gcd(375, 825) = 75.

Step 3 · The change needed

Change the last step to report the leftmost (first) element of common-divisors. Here that is 75, which is correct.

There is a bonus: since the first common divisor we meet is already the greatest, we can stop at the first one and need no list of common divisors at all.

Examining from n down to 1 gives decreasing lists, so the algorithm must report the leftmost common divisor (the first found) instead of the rightmost.

Chapter 11 Exercise 11.3 Question 2 Solution In the last algorithm (the one without lists) we scanned k from 2 up to min(m, n) and kept the most recent common divisor. What happens if we scan from min(m, n) down to 1?

Answer: the first hit is the gcd
The book's example of scanning up

Here is the last algorithm run upwards on m = 6 and n = 12. It must go through every k up to min(6, 12) = 6, and it keeps replacing the most recent common divisor.

The book's example for m equal to 6 and n equal to 12: scanning k from 2 to 6, the most recent common divisor becomes 2, then 3, stays 3, stays 3, and finally becomes 6, so gcd(6, 12) is 6.
Q2 · scanning up for gcd(6, 12), step by step (from the book)
Step 1 · The first common divisor found is the gcd

Going downwards, the first number k that divides both m and n is the greatest common divisor, because everything larger was already tried and failed. So we can stop immediately. We do not need most-recent-common-divisor at all.

  1. For each k from min(m, n) down to 1:
  2. if k divides both m and n, report k as the gcd and stop.
Step 2 · Count the checks
NumbersgcdChecks scanning up (2 to min)Checks scanning down (min to gcd)
375, 82575374301
54000, 810002700053,99927,001
1000, 100119991000

For 375 and 825: scanning down checks k = 375, 374, …, 75, which is 375 − 75 + 1 = 301 numbers. Scanning up checks 2 to 375, which is 374 numbers.

Scanning for gcd(375, 825) up and downScanning up checks all numbers from 2 to 375. Scanning down from 375 stops at 75, the gcd.Q2 · where each scan stops for gcd(375, 825)175150225300375scanning up: checks 2 to 375 (374 numbers)scanning down: stops at 75 (301 numbers)gcd = 75
Q2 · scanning down stops at the gcd (75), but scanning up must go all the way to 375
Step 3 · When it helps and when it does not

Scanning down saves work when the gcd is large, as in 375 and 825. When the gcd is small, such as 1, we must scan nearly all the way down, so there is no gain. The answer is always the same.

Scanning from min(m, n) down to 1, the first common divisor found is the gcd, and we can stop there. It saves work when the gcd is large (301 checks instead of 374 for 375 and 825).

Answers at a glance

Reversing the scan changes which end of the list holds the answer.

QuestionWhat is askedKey ideaAnswer
Q1 Divisors from n down to 1Decreasing listReport the leftmost, not the rightmost
Q2 Scan from min(m, n) downFirst hit is the gcdStop early; 301 vs 374 checks for 375, 825

Other chapters of Ganita Manjari (Class 9)

Source of the questions: NCERT, Ganita Manjari, Grade 9, Part II, Chapter 11, Exercise Set 11.3. The solutions, explanations and diagrams on this page are our own working.

Call WhatsApp Book Demo