SolveIt is under development
SolveItClass 9 · NCERT

NCERT Solutions · Class 9 Mathematics The World of Algorithms

15 questions · 15 still being checked

Exercise Set 11.3 1–2 (part 3 of 4)

  1. Exercise 1

    How would our original algorithm change if we computed the divisors of n\displaystyle n by examining the numbers from 1\displaystyle 1 to n\displaystyle n in reverse order, from n\displaystyle n down to 1\displaystyle 1?

    Not cross-checked

    This solution has not been cross-checked against the answer printed in NCERT.

    Only the scan direction changes, so the divisors are found largest first.1. Start with an empty list-of-divisors. 2. For each \(\displaystyle j\) in \(\displaystyle n, n-1, \ldots, 1\): if \(\displaystyle j\) divides \(\displaystyle n\), add \(\displaystyle j\) at the end.\[n=18:\ [\,] \to [18] \to [18,9] \to [18,9,6] \to [18,9,6,3] \to [18,9,6,3,2] \to [18,9,6,3,2,1] \]The gcd algorithm then builds common-divisors in decreasing order too, so Step $\displaystyle 5$ must report the leftmost element, not the rightmost.\[\text{common-divisors}(375,825) = [75,25,15,5,3,1] \;\Rightarrow\; \gcd(375,825)=75 \]Answer: The same divisors are found, but in decreasing order; in the gcd algorithm Step $\displaystyle 5$ reports the leftmost element instead of the rightmost.

  2. Exercise 2

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

    Not cross-checked

    This solution has not been cross-checked against the answer printed in NCERT.

    Going down from \(\displaystyle \min(m,n)\), the first \(\displaystyle k\) that divides both is already the gcd, so we stop there. Keeping the rule "update to the most recent" would fail: it keeps updating and ends at 1.\[m=6,\ n=12:\ k=6,3,2,1 \text{ all divide both} \;\Rightarrow\; \text{last update gives } 1 \neq \gcd(6,12)=6 \]Corrected algorithm: 1. Set \(\displaystyle k = \min(m,n)\). 2. If \(\displaystyle k\) divides both \(\displaystyle m\) and \(\displaystyle n\), report \(\displaystyle k\) and stop. 3. Otherwise decrease \(\displaystyle k\) by $\displaystyle 1$ and repeat Step 2.\[\gcd(6,12):\ k=6 \text{ divides both} \;\Rightarrow\; \text{answer 6 after 1 check (forward scan: 5 checks)} \]Since \(\displaystyle k=1\) always divides both, Step $\displaystyle 2$ always stops; no starting value is needed. Worst case, e.g. \(\displaystyle \gcd(100,97)\), still checks all $\displaystyle 97$ values.Answer: Scan \(\displaystyle k\) from \(\displaystyle \min(m,n)\) down to $\displaystyle 1$ and stop at the first \(\displaystyle k\) dividing both \(\displaystyle m\) and \(\displaystyle n\); that \(\displaystyle k\) is the gcd.