Ganita Manjari · Class 9 · Part II · Chapter 11

Ganita Manjari Class 9 Maths Chapter 11 The World of Algorithms End-of-Chapter Exercises Solutions

All 5 end-of-chapter questions: four gcd computations, a proof, and algorithms for primes, prime divisors and prime factorisation.

Last updated 6 October 2026

5Questions
1Diagrams
Ch 11The World of Algorithms

How to answer every question

Follow the rule exactly Write each step so that a reader can do it without guessing.
Name the lists Give each list or number a name and say what starts empty.
Execute on a small case Run the algorithm on a small example and write what happens.
Justify and count Say why the algorithm is correct and how many steps it needs.

Remainder (m mod n): what is left when m is divided by n.

Prime number: a number with exactly two divisors, 1 and itself.

Prime factorisation: writing a number as a product of primes, such as 2² × 3² × 5¹.

Euclid's algorithm

Chapter 11 End-of-Chapter Exercises Question 1 Solution : Compute (i) gcd(375, 825), (ii) gcd(51000, 81000), (iii) gcd(1789287, 237656), (iv) gcd(2587392, 157656) by the improved version of Euclid's algorithm.

Answer: 75, 3000, 1, 24

The rule: if m < n, reverse them. If n = 0, the answer is m. Otherwise replace gcd(m, n) by gcd(n, m mod n), where m mod n is the remainder when m is divided by n.

Part (i) · gcd(375, 825)75

The book carries out this algorithm in the long-division layout of Āryabhaṭa. Its Example 2 is exactly gcd(825, 375): 825 divided by 375 gives quotient 2 and remainder 75, and then 375 divided by 75 gives remainder 0, so the gcd is 75.

The book's three long-division examples. Example 2 shows gcd(825, 375) reduced to gcd(375, 75), with 375 divided by 75 leaving remainder 0, so the gcd is 75. — Q1 · the book's long-division examples; Example 2 is gcd(825, 375) (from the book)

Step	Problem	Division m = q × n + r	Next
1	gcd(375, 825)	m < n, so reverse	→ gcd(825, 375)
2	gcd(825, 375)	825 = 2 × 375 + 75	gcd(375, 75)
3	gcd(375, 75)	375 = 5 × 75 + 0	n = 0, answer 75

Q1(i) · 825 = 2 × 375 + 75 and 375 = 5 × 75, so the last block size 75 is the gcd

Part (ii) · gcd(51000, 81000)3000

Step	Problem	Division m = q × n + r	Next
1	gcd(51000, 81000)	m < n, so reverse	→ gcd(81000, 51000)
2	gcd(81000, 51000)	81000 = 1 × 51000 + 30000	gcd(51000, 30000)
3	gcd(51000, 30000)	51000 = 1 × 30000 + 21000	gcd(30000, 21000)
4	gcd(30000, 21000)	30000 = 1 × 21000 + 9000	gcd(21000, 9000)
5	gcd(21000, 9000)	21000 = 2 × 9000 + 3000	gcd(9000, 3000)
6	gcd(9000, 3000)	9000 = 3 × 3000 + 0	n = 0, answer 3000

The last non-zero remainder is 3000. Check: 51000 = 17 × 3000 and 81000 = 27 × 3000, and 17 and 27 have no common factor.

Part (iii) · gcd(1789287, 237656)1

Step	Problem	Division m = q × n + r	Next
1	gcd(1789287, 237656)	1789287 = 7 × 237656 + 125695	gcd(237656, 125695)
2	gcd(237656, 125695)	237656 = 1 × 125695 + 111961	gcd(125695, 111961)
3	gcd(125695, 111961)	125695 = 1 × 111961 + 13734	gcd(111961, 13734)
4	gcd(111961, 13734)	111961 = 8 × 13734 + 2089	gcd(13734, 2089)
5	gcd(13734, 2089)	13734 = 6 × 2089 + 1200	gcd(2089, 1200)
6	gcd(2089, 1200)	2089 = 1 × 1200 + 889	gcd(1200, 889)
7	gcd(1200, 889)	1200 = 1 × 889 + 311	gcd(889, 311)
8	gcd(889, 311)	889 = 2 × 311 + 267	gcd(311, 267)
9	gcd(311, 267)	311 = 1 × 267 + 44	gcd(267, 44)
10	gcd(267, 44)	267 = 6 × 44 + 3	gcd(44, 3)
11	gcd(44, 3)	44 = 14 × 3 + 2	gcd(3, 2)
12	gcd(3, 2)	3 = 1 × 2 + 1	gcd(2, 1)
13	gcd(2, 1)	2 = 2 × 1 + 0	n = 0, answer 1

The remainders shrink 125695, 111961, 13734, 2089, 1200, 889, 311, 267, 44, 3, 2, 1, 0. The last non-zero remainder is 1, so the two numbers have no common factor other than 1 (they are co-prime).

Part (iv) · gcd(2587392, 157656)24

Step	Problem	Division m = q × n + r	Next
1	gcd(2587392, 157656)	2587392 = 16 × 157656 + 64896	gcd(157656, 64896)
2	gcd(157656, 64896)	157656 = 2 × 64896 + 27864	gcd(64896, 27864)
3	gcd(64896, 27864)	64896 = 2 × 27864 + 9168	gcd(27864, 9168)
4	gcd(27864, 9168)	27864 = 3 × 9168 + 360	gcd(9168, 360)
5	gcd(9168, 360)	9168 = 25 × 360 + 168	gcd(360, 168)
6	gcd(360, 168)	360 = 2 × 168 + 24	gcd(168, 24)
7	gcd(168, 24)	168 = 7 × 24 + 0	n = 0, answer 24

The last non-zero remainder is 24. Check: 2587392 = 107808 × 24 and 157656 = 6569 × 24.

(i) 75, (ii) 3000, (iii) 1, (iv) 24. Even for 7-digit numbers, the division version needed only 13 steps at most.

Chapter 11 End-of-Chapter Exercises Question 2 Solution : Assume m ≥ n. Verify that d divides both m and n if and only if d divides both n and m mod n.

Answer: proved both ways

Setting up

Divide m by n: m = q × n + r, where q is the quotient and r = m mod n is the remainder, with 0 ≤ r < n. So r = m − q × n.

The picture behind the idea

The book's Fig. 11.1 shows the same idea for subtraction: if blocks of size d tile both m and n, they also tile m − n. Taking away n again and again from m leaves m mod n, so the picture works for the remainder too.

Two rows of blocks of size d. The top row has length m. The bottom row is split into a part of length n and a part of length m minus n, and both parts are tiled by blocks of size d. — Q2 · Fig. 11.1 of the book: blocks of size d tile m, n and m − n (from the book)

Step 1 · If d divides m and n, then d divides n and r

Write m = ad and n = bd. Then r = m − qn = ad − q(bd) = (a − qb)d. So d divides r, and d also divides n. Therefore d divides both n and m mod n.

Step 2 · If d divides n and r, then d divides m and n

Write n = xd and r = yd. Then m = qn + r = q(xd) + yd = (qx + y)d. So d divides m, and d also divides n. Therefore d divides both m and n.

A numerical check

Take m = 825 and n = 375. Then r = 825 mod 375 = 75, since 825 = 2 × 375 + 75.

d	Divides 825 and 375?	Divides 375 and 75?
25	yes	yes
75	yes	yes
11	no (11 does not divide 375)	no (11 does not divide 75)
125	no (125 does not divide 825)	no (125 does not divide 75)

The common divisors of m and n are exactly the common divisors of n and m mod n, so gcd(m, n) = gcd(n, m mod n), which justifies the improved algorithm. (Proving both directions is the idea of an "if and only if" statement; see Chapter 9 Propositions and their Converses Solutions.)

Primes

Chapter 11 End-of-Chapter Exercises Question 3 Solution : Write an algorithm prime(n) to check if n is prime. (Hint: a prime p has exactly two divisors, 1 and p. Use divisors(n).)

Answer: prime when divisors(n) has 2 elements

Algorithm prime(n)

Let list-of-divisors be the list obtained by computing divisors(n).
If list-of-divisors has exactly two elements, report "n is prime".
Otherwise report "n is not prime".

Execute it on examples

n	divisors(n)	Elements	Result
13	[1, 13]	2	prime
15	[1, 3, 5, 15]	4	not prime
2	[1, 2]	2	prime
1	[1]	1	not prime

n = 1 has only one divisor, so it is not prime, and the algorithm correctly says so.

A quicker version

We can stop early. If any j from 2 to n − 1 divides n, report "not prime" and stop. If none does, report "prime" (for n larger than 1).

prime(n): compute divisors(n); if it has exactly two elements (1 and n), n is prime, otherwise it is not.

Chapter 11 End-of-Chapter Exercises Question 4 Solution : Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers. (Hint: compute divisors(n) and filter out the primes.)

StarredAnswer: filter divisors(n) with prime

Algorithm primedivisors(n)

Let divisors-of-n be the list obtained by computing divisors(n).
Start with an empty list prime-divisors.
For each d in divisors-of-n: if prime(d) says d is prime, add d to prime-divisors.
Report prime-divisors.

Execute it for n = 180

divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]. Test each one with prime(d).

d	Number of divisors of d	Prime?
1	1	no
2	2	yes
3	2	yes
4	3	no
5	2	yes
6	4	no
9	3	no
10	4	no
12	6	no
15	4	no
18	6	no
20	6	no
30	8	no
36	9	no
45	6	no
60	12	no
90	12	no
180	18	no

Only 2, 3 and 5 have exactly two divisors.

primedivisors(180) = [2, 3, 5]. The algorithm lists divisors(n) and keeps those d for which prime(d) is true.

Chapter 11 End-of-Chapter Exercises Question 5 Solution : 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?

StarredAnswer: list of (prime, exponent) pairs

The algorithm

Start with an empty list factors. Let r = n and p = 2.
As long as r is bigger than 1: if p divides r, add p to factors and replace r by rp. Otherwise, add 1 to p.
Report factors.

Execute it for n = 180

r	p	Does p divide r?	factors	New r
180	2	yes	[2]	90
90	2	yes	[2, 2]	45
45	2	no	[2, 2]	45 (p becomes 3)
45	3	yes	[2, 2, 3]	15
15	3	yes	[2, 2, 3, 3]	5
5	3	no	[2, 2, 3, 3]	5 (p becomes 4)
5	4	no	[2, 2, 3, 3]	5 (p becomes 5)
5	5	yes	[2, 2, 3, 3, 5]	1

r has become 1, so we stop. The composite 4 never divides r, because all the 2s were already removed. So p only ever stops at primes.

Part (i) · How to represent 180 = 2² × 3² × 5¹

Write a list of pairs (prime, exponent), in increasing order of the prime.

180 → [(2, 2), (3, 2), (5, 1)]

Count equal entries of factors: 2 appears twice, 3 twice, 5 once.

Part (ii) · Comparing two factorisations to get the gcd

Go through both lists. For every prime that appears in both, keep the smaller exponent. Multiply these powers to get the gcd.

Numbers	Factorisations	Common primes with smaller exponent	gcd
375 and 825	375 → [(3, 1), (5, 3)]; 825 → [(3, 1), (5, 2), (11, 1)]	3¹ and 5²	3 × 25 = 75
180 and 150	180 → [(2, 2), (3, 2), (5, 1)]; 150 → [(2, 1), (3, 1), (5, 2)]	2¹, 3¹ and 5¹	2 × 3 × 5 = 30

Both answers agree with Euclid's algorithm. A prime that appears in only one number (like 11 above) does not go into the gcd.

Factorise by trying p = 2, 3, 4, … and dividing out. Store 180 as [(2, 2), (3, 2), (5, 1)]. For the gcd, multiply each common prime to its smaller exponent.

Answers at a glance

The gcd questions use the improved Euclid algorithm; the others build algorithms from earlier ones.

Question	What is asked	Key idea	Answer
Q1	Four gcds	Repeat gcd(n, m mod n)	75, 3000, 1, 24
Q2	Verify the divisor claim	m = q × n + r	Proved both ways
Q3	Is n prime?	divisors(n) has 2 elements	prime(n) algorithm
Q4	Prime divisors of n	Filter divisors with prime	[2, 3, 5] for 180
Q5	Prime factorisation	Divide out p = 2, 3, …	[(2, 2), (3, 2), (5, 1)]; gcd by min exponents

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

d	Number of divisors of d	Prime?
1	1	no
2	2	yes
3	2	yes
4	3	no
5	2	yes
6	4	no
9	3	no
10	4	no
12	6	no
15	4	no
18	6	no
20	6	no
30	8	no
36	9	no
45	6	no
60	12	no
90	12	no
180	18	no

d	Number of divisors of d	Prime?
1	1	no
2	2	yes
3	2	yes
4	3	no
5	2	yes
6	4	no
9	3	no
10	4	no
12	6	no
15	4	no
18	6	no
20	6	no
30	8	no
36	9	no
45	6	no
60	12	no
90	12	no
180	18	no

How to answer every question

Euclid's algorithm

Primes

Answers at a glance

More Chapter 11 The World of Algorithms solutions

Other chapters of Ganita Manjari (Class 9)

d	Number of divisors of d	Prime?
1	1	no
2	2	yes
3	2	yes
4	3	no
5	2	yes
6	4	no
9	3	no
10	4	no
12	6	no
15	4	no
18	6	no
20	6	no
30	8	no
36	9	no
45	6	no
60	12	no
90	12	no
180	18	no