NCERT Solutions for Class 9 Maths Chapter 11 — Exercise Set 11.3#

Recall the two versions of the gcd algorithm in this section:

  • Original: list the divisors of $m$ and of $n$ in increasing order, list their common divisors, and report the rightmost one.
  • Last version: start with most-recent-common-divisor = 1, scan $k$ from 2 up to $\min(m, n)$, and update it whenever $k$ divides both numbers.

1. 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? #

Solution

Checking from $n$ down to 1, the divisors are added to the list in decreasing order, for example divisors(18) = [18, 9, 6, 3, 2, 1].

If we do this for both numbers, the list of common divisors is also in decreasing order, for example [75, 25, 15, 5, 3, 1] for 375 and 825. The gcd is now the leftmost (first) element, not the rightmost.

So the last step changes to: “Report the leftmost element of common-divisors as gcd(m, n).”

(If only one of the two lists were reversed, the common divisors would follow the order of whichever list we scan, so we must be careful to report the largest element.)

2. What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1? #

Solution

Scanning $k = \min(m, n), \min(m, n) - 1, \ldots, 2, 1$, the first $k$ that divides both $m$ and $n$ is the greatest common divisor — every later $k$ is smaller.

So we no longer need to keep updating a value until the end. The algorithm becomes:

  1. For each $k$ from $\min(m, n)$ down to 1:
    • if $k$ divides both $m$ and $n$, report $k$ as gcd(m, n) and stop.

This always stops, because $k = 1$ divides every number. It can be much faster: for gcd(6, 12) it stops at once at $k = 6$; for gcd(375, 825) it checks 375 down to 75. But in the worst case (when the gcd is 1) it still checks every number down to 1.

Quick links