NCERT Solutions Class 9 Mathematics Ganita Manjari 2 Chapter 11 The World of Algorithms End of Chapter Exercises

End-of-Chapter Exercises

Question 1. Compute the following using the improved version of Euclid's algorithm.
(i) gcd(375, 825)
(ii) gcd(51000, 81000)
(iii) gcd(1789287, 237656)
(iv) gcd(2587392, 157656)
Answer:
Improved (division) algorithm: if m < n, swap the numbers; if n = 0, the answer is m; otherwise replace gcd(m, n) by gcd(n, m mod n).
(i) 375 < 825, so first swap: we find gcd(825, 375).
Step 1: 825 = 2 × 375 + 75  ⇒  gcd(825, 375) = gcd(375, 75)
Step 2: 375 = 5 × 75 + 0  ⇒  gcd(375, 75) = gcd(75, 0)

gcd(375, 825) = 75. (Only 2 reductions, against 7 by repeated subtraction.)
(ii) 51000 < 81000, so we find gcd(81000, 51000).
Step 1: 81000 = 1 × 51000 + 30000  ⇒  gcd(81000, 51000) = gcd(51000, 30000)
Step 2: 51000 = 1 × 30000 + 21000  ⇒  gcd(51000, 30000) = gcd(30000, 21000)
Step 3: 30000 = 1 × 21000 + 9000  ⇒  gcd(30000, 21000) = gcd(21000, 9000)
Step 4: 21000 = 2 × 9000 + 3000  ⇒  gcd(21000, 9000) = gcd(9000, 3000)
Step 5: 9000 = 3 × 3000 + 0  ⇒  gcd(9000, 3000) = gcd(3000, 0)

gcd(51000, 81000) = 3000. Check: 51000 = 17 × 3000 and 81000 = 27 × 3000, and 17 and 27 have no common factor other than 1.
(iii) m = 1789287 > n = 237656, so no swap is needed.
Step 1: 1789287 = 7 × 237656 + 125695  ⇒  gcd(1789287, 237656) = gcd(237656, 125695)
Step 2: 237656 = 1 × 125695 + 111961  ⇒  gcd(237656, 125695) = gcd(125695, 111961)
Step 3: 125695 = 1 × 111961 + 13734  ⇒  gcd(125695, 111961) = gcd(111961, 13734)
Step 4: 111961 = 8 × 13734 + 2089  ⇒  gcd(111961, 13734) = gcd(13734, 2089)
Step 5: 13734 = 6 × 2089 + 1200  ⇒  gcd(13734, 2089) = gcd(2089, 1200)
Step 6: 2089 = 1 × 1200 + 889  ⇒  gcd(2089, 1200) = gcd(1200, 889)
Step 7: 1200 = 1 × 889 + 311  ⇒  gcd(1200, 889) = gcd(889, 311)
Step 8: 889 = 2 × 311 + 267  ⇒  gcd(889, 311) = gcd(311, 267)
Step 9: 311 = 1 × 267 + 44  ⇒  gcd(311, 267) = gcd(267, 44)
Step 10: 267 = 6 × 44 + 3  ⇒  gcd(267, 44) = gcd(44, 3)
Step 11: 44 = 14 × 3 + 2  ⇒  gcd(44, 3) = gcd(3, 2)
Step 12: 3 = 1 × 2 + 1  ⇒  gcd(3, 2) = gcd(2, 1)
Step 13: 2 = 2 × 1 + 0  ⇒  gcd(2, 1) = gcd(1, 0)

gcd(1789287, 237656) = 1. The two numbers are co-prime. Even for 7-digit numbers only 13 reductions were needed.
(iv) m = 2587392 > n = 157656.
Step 1: 2587392 = 16 × 157656 + 64896  ⇒  gcd(2587392, 157656) = gcd(157656, 64896)
Step 2: 157656 = 2 × 64896 + 27864  ⇒  gcd(157656, 64896) = gcd(64896, 27864)
Step 3: 64896 = 2 × 27864 + 9168  ⇒  gcd(64896, 27864) = gcd(27864, 9168)
Step 4: 27864 = 3 × 9168 + 360  ⇒  gcd(27864, 9168) = gcd(9168, 360)
Step 5: 9168 = 25 × 360 + 168  ⇒  gcd(9168, 360) = gcd(360, 168)
Step 6: 360 = 2 × 168 + 24  ⇒  gcd(360, 168) = gcd(168, 24)
Step 7: 168 = 7 × 24 + 0  ⇒  gcd(168, 24) = gcd(24, 0)

gcd(2587392, 157656) = 24. Check: 2587392 = 24 × 107808 and 157656 = 24 × 6569.

Teacher's Note:
1. In the long-division layout each remainder becomes the next divisor, and the last non-zero remainder (the last divisor) is the gcd.
2. Part (iii) shows the power of the method: 13 divisions settle a question that would need over two lakh tests by listing divisors.

Question 2. Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.
Answer:
Divide m by n: let the quotient be q and the remainder r = m mod n. Then m = qn + r, with 0 ≤ r < n.

Two directions have to be shown.
Part 1: if d divides m and n, then d divides n and m mod n.
Write m = ad and n = bd for whole numbers a and b. Then
r = m − qn = ad − q(bd) = (a − qb)d.
So r is a multiple of d (if r = 0, it is 0 × d). Hence d divides m mod n, and d divides n already.
Part 2: if d divides n and m mod n, then d divides m and n.
Write n = xd and r = yd for whole numbers x and y. Then
m = qn + r = q(xd) + yd = (qx + y)d.
So d divides m, and d divides n.
In the picture: m is q copies of n followed by the leftover piece m mod n. If blocks of size d exactly fill both m and n, removing the q copies of n leaves a piece that is still exactly filled, namely m mod n. Conversely, if d fills n and m mod n, putting q copies of n and m mod n side by side fills m.
Numerical check: m = 825, n = 375, 825 = 2 × 375 + 75, so m mod n = 75.
d = 25: divides 825, 375 and 75. d = 75: divides 825, 375 and 75. d = 11: divides 825 but not 375 or 75. d = 125: divides 375 but not 825 or 75.
In every case, "divides both 825 and 375" holds exactly when "divides both 375 and 75" holds.
Hence d divides m and n if and only if d divides n and m mod n. So the pairs (m, n) and (n, m mod n) have the same common divisors, which is why gcd(m, n) = gcd(n, m mod n).

Teacher's Note:
1. "If and only if" always needs two separate proofs, one in each direction.
2. This result is the reason Euclid's division algorithm is correct: each reduction keeps the set of common divisors unchanged.

Question 3. Write an algorithm prime(n) to check if n is prime.
(Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?)
Answer:
A prime number has exactly two different divisors, 1 and itself. So compute its divisors and count them.
Algorithm prime(n)
1. Let list-of-divisors = divisors(n).
2. If list-of-divisors has exactly two elements, report "n is prime".
3. Otherwise, report "n is not prime".
Trying it out:
n = 1: divisors [1], 1 element → not prime.
n = 13: divisors [1, 13], 2 elements → prime.
n = 15: divisors [1, 3, 5, 15], 4 elements → not prime.
n = 31: divisors [1, 31], 2 elements → prime.
Note that the algorithm correctly says 1 is not prime, since 1 has only one divisor.
A quicker version. We do not need every divisor: n fails to be prime as soon as any divisor between 2 and n − 1 turns up, and (Exercise Set 11.2, Q3) it is enough to look up to √n.
1. If n = 1, report "n is not prime".
2. For each j = 2, 3, 4, … as long as j × j ≤ n:
    — if j divides n, report "n is not prime" and stop.
3. Report "n is prime".
For example, for n = 97 we test only j = 2, 3, …, 9 (since 9 × 9 = 81 ≤ 97 < 100). None divides 97, so 97 is prime.

Question 4. Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
(Hint: Compute divisors(n) and then filter out the primes in this list.)
Answer:
Algorithm primedivisors(n)
1. Let divisors-of-n = divisors(n).
2. Start with an empty list prime-divisors.
3. For each number x in divisors-of-n:
    — if prime(x) reports "x is prime", add x to prime-divisors.
4. Report prime-divisors.
It uses divisors(n) from the chapter and prime(x) from Question 3. As divisors-of-n is in increasing order, prime-divisors is also in increasing order.
Example: n = 180.
divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180].
Testing each: 2, 3 and 5 are prime; 1, 4, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180 are not.
primedivisors(180) = [2, 3, 5].
Similarly, primedivisors(375) = [3, 5] and primedivisors(825) = [3, 5, 11].

Question 5. We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.
(i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?
Answer:
For each prime divisor p of n we must find how many times p divides n (its exponent). We get this by dividing by p again and again.
Algorithm factorisation(n)
1. Let primes = primedivisors(n).
2. Start with an empty list factors, and let current = n.
3. For each prime p in primes:
    — set count to 0;
    — while p divides current, replace current by current ÷ p and add 1 to count;
    — add the pair (p, count) to factors.
4. Report factors.
Running it for n = 180: primedivisors(180) = [2, 3, 5].
p = 2: 180 ÷ 2 = 90, 90 ÷ 2 = 45 (2 does not divide 45) → count 2, factors = [(2, 2)].
p = 3: 45 ÷ 3 = 15, 15 ÷ 3 = 5 (3 does not divide 5) → count 2, factors = [(2, 2), (3, 2)].
p = 5: 5 ÷ 5 = 1 (5 does not divide 1) → count 1, factors = [(2, 2), (3, 2), (5, 1)].
(i) Represent 180 = 2² × 3² × 5¹ as a list of pairs (prime, exponent), primes in increasing order:
180 → [(2, 2), (3, 2), (5, 1)]
The first entry of each pair is the prime and the second its power. Check: 2² × 3² × 5¹ = 4 × 9 × 5 = 180.
(ii) Go through the two lists of pairs together, as in Exercise Set 11.2, Q1 (both are in increasing order of primes).
A prime that appears in only one list has power 0 in the other number. A prime p divides both numbers only if it appears in both lists, and the highest power of p dividing both is p raised to the smaller of the two exponents.
Algorithm gcd using prime factorisations
1. Compute factorisation(m) and factorisation(n).
2. Start with g = 1.
3. For each pair (p, a) in factorisation(m):
    — if a pair (p, b) with the same prime p is in factorisation(n), multiply g by p raised to the smaller of a and b.
4. Report g as gcd(m, n).
Example 1: gcd(180, 825).
180 = 2² × 3² × 5¹ → [(2, 2), (3, 2), (5, 1)]; 825 = 3¹ × 5² × 11¹ → [(3, 1), (5, 2), (11, 1)].
Prime 2: powers 2 and 0 → 0; prime 3: powers 2 and 1 → 1; prime 5: powers 1 and 2 → 1; prime 11: powers 0 and 1 → 0.
gcd(180, 825) = 3¹ × 5¹ = 15.
Check by division: 825 = 4 × 180 + 105, 180 = 1 × 105 + 75, 105 = 1 × 75 + 30, 75 = 2 × 30 + 15, 30 = 2 × 15 + 0, so the gcd is 15.
Example 2: 375 = 3¹ × 5³ and 825 = 3¹ × 5² × 11¹, so gcd(375, 825) = 3¹ × 5² = 75.
(Taking the larger power of every prime instead gives the lcm: lcm(180, 825) = 2² × 3² × 5² × 11¹ = 9900.)
Note: this method needs the prime factorisations first, which means finding divisors — work that grows with the size of the numbers. So Āryabhaṭa's division method is far faster for large numbers.

Teacher's Note:
1. Representing a factorisation as a list of (prime, exponent) pairs is a data-structure choice; ask students why the primes should be kept in increasing order.
2. Smaller exponent gives the gcd, larger exponent gives the lcm; this is a neat check that gcd × lcm = m × n.