Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari)
Master Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) with comprehensive NCERT Solutions, Practice Questions, MCQs, Sample Papers, Case Based Questions, and Video lessons.
NCERT Solutions
Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) – NCERT Solutions
Each question below opens its complete step-by-step Teachoo solution.
Exercise Set 11.1
5 questionsEx 11.1, 1
Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?
We are talking about these steps
Ex 11.1, 2
What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
Consider
12345 + 678
Align the numbers from the right
Ten-thousands | Thousands | Hundreds | Tens | Units
1 | 2 | 3 | 4 | 5
— | — | 6 | 7 | 8
Ex 11.1, 3
Why is it important to align the columns from right to left?
For whole numbers, rightmost digit represents units. The next digit represents tens, followed by hundreds, and so on.
Aligning from right to left guarantees that units are added to units, tens to tens, and hundreds to hundreds.
If you aligned from left to right (e.g., aligning the 3 of 34512 with the 6 of 678), you would mistakenly add 6 hundreds to 3 ten-thousands.
Ex 11.1, 4
In Step 3, why cannot the value of carry be more than 1?
We are talking about these steps
Now, our digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Ex 11.1, 5
What happens if we do not include the fifth step in the algorithm above? Give examples where the algorithm will work correctly and where it will fail to work.
We are talking about these steps
Step 5 writes the final carry on the left
Exercise Set 11.2
4 questionsEx 11.2, 1
(i)
Suppose List 1 and List 2 are two lists of numbers in increasing order.
(i) Write an algorithm to find elements in List 1 that are not present in List 2.
We must keep an entry only when it belongs to the first list and is absent from the second.
Algorithm
Start with an empty list only-in-list-1
For each number x in List 1
If x does not appear in List 2, add x to the end of only-in-list-1
Report only-in-list-1
Example
Ex 11.2, 2
Describe an algorithm to compute the least common multiple (1cm) of two numbers.
There are two ways in which we can find least common multiple (1cm) of two numbers
Direct Method - from definition
Indirect Method – using formula LCM(m, n) × GCD (m, n) = m × n
Let’s do both
Direct Method
The least common multiple, or LCM, is the smallest positive number which is multiple of both numbers
LCM of 4 and 6
Multiples of 4=4, 8, 12, 16, 20, 24,…
Multiples of 6=6, 12, 18, 24,…[ ; ]
The smallest common multiple is 12
So,
𝐥𝐜𝐦(𝟒, 𝟔)=𝟏𝟐
Constructing the algorithm
Since multiples can go on and on until infinity, we need to find a way to stop
Let’s follow this
Find multiples of the larger number in increasing order
Check if each multiple is also a multiple of the smaller number
Stop at the first number which satisfies this
We can write the algorithm now
Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏)
Let a be the larger of m, n, and b the smaller
If m = n, LCM = m = n
Set candidate to a
If candidate is divisible by b, candidate is the LCM. Stop here.
Otherwise, increase candidate by a
Repeat Steps 3 and 4.
Example: Find lcm(8,12)
Step 1: Identify the greater and smaller numbers
𝑎=18, 𝑏=12
Step 2: Set the first candidate
candidate =18
Step 3: Check whether 12 divides 18
(18)/(12)=1(6)/(12)
The remainder is 6 , so 12 does not divide 18
Therefore, 18 is not a common multiple
Step 4: Increase candidate by a (Move to the next multiple of 18)
candidate = 18 + 18 = 18 × 2 = 36
Step 5: Check whether 12 divides 36
(36)/(12)=3
Since the remainder is 0, so 12 divides 36.
So, we stop here
Thus,
𝐥𝐜𝐦(𝟏𝟐, 𝟏𝟖)=𝟑𝟔
Let’s do the indirect Method now
Indirect Method
For two positive integers:
𝐥𝐜𝐦(𝒎,𝒏) × 𝐠𝐜𝐝(𝒎,𝒏)=𝒎 ×𝒏
Dividing both sides by gcd(𝑚,𝑛) :
lcm(𝑚,𝑛)=(𝑚 × 𝑛)/(gcd(𝑚, 𝑛))
This gives us a different plan:
Find the GCD using an algorithm we already know.
Divide the product of the inputs by that GCD.
Algorithm to find 𝐥𝐜𝐦(𝒎,𝒏) using the GCD
Compute 𝐠𝐜𝐝(𝒎,𝒏) using a GCD algorithm.
Store this value as 𝑔
Compute:
𝐿=((𝑚)/(𝑔)) × 𝑛
Report 𝐿 as lcm(𝑚,𝑛)
Example: Find lcm(8,12)
Step 1: Find gcd (8, 12)
𝑎=18, 𝑏=12
Ex 11.2, 3 (i)
Divisors occur in pairs. For instance, the divisors of 18 are (1, 18),
(2, 9) and (3, 6).
(i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n?
For n = 18
The divisor pairs are (1, 18), (2, 9) and (3, 6)
This means,
18 = 1 × 18 = 2 × 9 = 3 × 6
Now,
If we find a divisor 𝒋,
Partner of j in divisor pair = (𝒏)/(𝒋)
Ex 11.2, 3 (ii)
Divisors occur in pairs. For instance, the divisors of 18 are (1, 18),
(2, 9) and (3, 6).
(ii) If we list out the divisors in pairs, will our gcd algorithm still work
in the manner we have described?
Not necessarily.
Its final step depends on the list being in increasing order
For 18, appending divisors pair by pair gives
[1, 18, 2, 9, 3, 6]
This list is not increasing
For 36, pairwise listing gives:
[𝟏,𝟑𝟔,𝟐,𝟏𝟖,𝟑,𝟏𝟐,𝟒,𝟗,𝟔]
Applying the original GCD algorithm to 18 and 36
Every divisor of 18 appears in the list for 36, so the common-divisor list becomes:
[𝟏, 𝟏𝟖, 𝟐, 𝟗, 𝟑 ,𝟔]
The original final step says:
Report the rightmost entry.
That would report 6 , which is wrong:
gcd(18,36)=18
What exactly went wrong?
Finding the divisors in pairs was correct. Identifying the common divisors was also correct.
The failure occurred because "rightmost" no longer meant "greatest.”
Two ways to fix it
asd
Exercise Set 11.3
2 questionsEx 11.3, 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?
Previously, we checked candidates in increasing order:
1, 2, 3,…,𝑛
Appending each successful candidate produced an increasing divisor list.
If we instead check:
𝒏,𝒏−𝟏,𝒏−𝟐,…,𝟏
and continue appending successful candidates to the end, the list will be decreasing.
Example: Divisors of 18
We examine 18, 17, . . , 1 .
The successful candidates appear in this order:
18, 9, 6, 3, 2, 1
Therefore:
divisors (𝟏𝟖)=[18, 9, 6, 3, 2, 1]
Similarly:
divisors (𝟐𝟒)=[24, 12, 8, 6, 4, 3, 2, 1]
Now examine the divisors of 18 in order and retain those appearing in the list for 24
Ex 11.3, 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?
The last algorithm described above is
Final improved algorithm for gcd
Set most-recent-common-divisor to 1.
For each number 𝑘 from 2 to min(𝑚,𝑛) :
If 𝑘 divides both 𝑚 and 𝑛, set most-recent-common-divisor to 𝑘.
Report most-recent-common-divisor as gcd(𝑚,𝑛)
In the last algorithm,
We store only the most recently found common divisor
End-of-Chapter Exercises
8 questionsQuestion 1 (i)
Compute the following using the improved version of Euclid’s algorithm.
(i) gcd(375, 825)
Larger number should be first. So, we write
gcd(375, 825) = gcd(825, 375)
Finding remainder after doing (𝟖𝟐𝟓)/(𝟑𝟕𝟓)
Question 1 (ii)
Compute the following using the improved version of Euclid’s algorithm.
(ii) gcd(51000, 81000)
Larger number should be first. So, we write
gcd(51000, 81000) = gcd(81000, 51000)
Finding remainder after doing (𝟖𝟏𝟎𝟎𝟎)/(𝟓𝟏𝟎𝟎𝟎)
Question 1 (iii)
Compute the following using the improved version of Euclid’s algorithm.
(iii) gcd(1789287, 237656)
Larger number should be first, which is the case here
Finding remainder after doing (𝟏𝟕𝟖𝟗𝟐𝟖𝟕)/(𝟐𝟑𝟕𝟔𝟓𝟔)
Question 1 (iv)
Compute the following using the improved version of Euclid’s algorithm.
(iv) gcd(2587392, 157656)
Larger number should be first, which is the case here
Finding remainder after doing (𝟐𝟓𝟖𝟕𝟑𝟗𝟐)/(𝟏𝟓𝟕𝟔𝟓𝟔)
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.
An “if and only if” statement requires proving both directions
First direction – Suppose d divides m and n, we prove that d divides both n and m mod n
Second direction – Suppose d divides m and m mod n, we prove that d divides both m and n
Let
Remainder = r = m mod n
Since m ≥ n, we can write
m = qn + r
Where r = m mod n
And,
0 ≤ r < n
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)?)
A prime number is an integer greater than 1 having exactly two distinct positive divisors:
1 and the number itself
We already have an algorithm divisors (𝒏), so we can reuse it.
How we arrive at the algorithm
Find all positive divisors of 𝑛
Count them
If there are exactly two, 𝑛 is prime
Otherwise, it is not prime
Algorithm to check whether 𝒏 is prime
If 𝑛<2, report "not prime" and stop
Let list-of-divisors be the list obtained by computing
divisors (𝑛)
Count the entries in list-of-divisors
If there are exactly two entries, report "prime"
Otherwise, report "not prime"
Example 1: 𝒏=𝟏𝟑
divisors (13)=[1, 13]
There are exactly two entries
∴ 13 is prime
Example 2: 𝒏=𝟏𝟐
divisors (12)=[1, 2, 3, 4, 6, 12]
There are six entries
So, 12 is not prime
Example 3: 𝒏=𝟏
Since 1<2, report "not prime"
Let’s check divisors
divisors(1) = [1]
Since it has only one entry
So, 1 is not 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.)
We want a list containing the divisors of 𝑛 that are prime.
For example, 12 has divisors:
divisors (2) = [1, 2, 3, 4, 6, 12]
Only 2 and 3 are prime, so:
primedivisors(12) =[𝟐, 𝟑]
How we arrive at the algorithm
We already know how to:
Find divisors using divisors (𝒏)
Test if prime using prime (𝒙)
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?
Prime factorisation expresses a positive integer greater than 1 as a product of primes, including repeated factors.
For example:
𝟏𝟖𝟎=𝟐 × 𝟐 × 𝟑 × 𝟑 × 𝟓
How we arrive at the algorithm
From Question 4, we can find the distinct prime divisors.
For each prime divisor, repeatedly divide it out. Count how many times the division succeeds.
That count is its exponent in the factorisation.
Algorithm to compute the prime factorisation of
Why Learn This With Teachoo?
Learn Chapter 11: The World of Algorithms from NCERT Ganita Manjari, Class 9 Maths, Part II, with Teachoo. Understand how to write clear mathematical procedures, execute them step by step, explain why they work and improve their efficiency.
You already use algorithms when you add numbers column by column or find factors systematically. This chapter takes those familiar methods further: how can you describe every step precisely? What information should you keep track of? How can you find the greatest common divisor (GCD), also called the highest common factor (HCF), without checking every possible divisor?
Teachoo helps you connect familiar arithmetic with these new ideas, making algorithms easier to understand through worked reasoning and clear explanations. Use Teachoo to study the concepts, practise Exercise Sets 11.1–11.3, and approach the End-of-Chapter Exercises with confidence.
What will you learn in Chapter 11?
Addition as an algorithm
Explore how digit-by-digit addition works using place value and carrying. Learn why numbers must be aligned correctly, why every possible case needs an instruction, and why a final carry cannot be ignored.
Finding divisors and the GCD or HCF
Learn to list the divisors of a number, identify the common divisors of two numbers, and select the greatest one. Understand how to turn the definition of GCD into a systematic procedure.
Data structures and keeping track of information
Understand how named quantities and lists help an algorithm store and organise intermediate results. See why the order of a list matters when selecting its largest element.
Improving an algorithm
Explore ways to reduce repeated work, check fewer possible divisors and avoid storing information you no longer need.
Euclid’s subtraction algorithm
Learn why subtracting the smaller number from the larger one preserves their GCD, and how repeated subtraction reduces the original problem to simpler problems.
Āryabhaṭa’s division algorithm
Study the remainder-based method presented in the chapter as Āryabhaṭa’s Division Algorithm. Understand how division replaces many repeated subtractions and leads to a more efficient GCD calculation.
With Teachoo, focus on four questions throughout the chapter: What are the steps? Why are they correct? When do they stop? How much work do they require?
What is an algorithm?
An algorithm is a precisely described, step-by-step procedure for solving a problem.
For example, an algorithm for listing the positive divisors of a positive integer n can:
-
Start with an empty list.
-
Check each integer from 1 to n.
-
Add an integer to the list if it divides n exactly.
-
Report the completed list.
For n = 18, the result is [1, 2, 3, 6, 9, 18].
An algorithm may contain repeated steps and conditional instructions. What matters is that you can follow its instructions consistently and obtain the intended result.
Understand the division algorithm with an example
Find GCD(60, 16) using division and remainders:
60 = 16 × 3 + 12
16 = 12 × 1 + 4
12 = 4 × 3 + 0
The last non-zero remainder is 4, so:
GCD(60, 16) = HCF(60, 16) = 4
The key relationship is:
GCD(m, n) = GCD(n, m mod n), where n > 0
Here, m mod n means the remainder when m is divided by n.
Teachoo helps you understand why this relationship works, so that the calculation becomes a logical sequence rather than a rule to memorise.
Exercise Sets 11.1–11.3 and End-of-Chapter Exercises
Ganita Manjari Class 9 Chapter 11 contains three exercise sets—11.1, 11.2 and 11.3—followed by End-of-Chapter Exercises.
-
Exercise Set 11.1: Examine the addition algorithm, test its instructions, and reason about alignment and carrying.
-
Exercise Set 11.2: Describe procedures for comparing lists and finding the LCM, and investigate divisor pairs.
-
Exercise Set 11.3: Explore how checking numbers in reverse order changes divisor lists and GCD procedures.
-
End-of-Chapter Exercises: Calculate GCDs using the improved algorithm, justify the remainder relationship, and design algorithms for checking primes, finding prime divisors and computing prime factorisations.
These questions ask you to explain and design procedures as well as calculate answers. Teachoo helps you build that understanding progressively.
Why study The World of Algorithms with Teachoo?
An algorithm can look correct but still leave an important case unspecified. It can also produce the right answer while doing much more work than necessary.
Teachoo teaches you to examine both correctness and efficiency. You learn to follow instructions precisely, track changing values, identify missing cases and explain improvements.
You do not need prior programming knowledge to begin. Start with the addition methods you already know, then build towards divisor lists and the GCD algorithms. Make Teachoo your go-to learning platform for Ganita Manjari Class 9 Maths, with a clear path from familiar calculations to confident mathematical reasoning.
Frequently asked questions
1. What is Chapter 11 in Class 9 Ganita Manjari?
Chapter 11 in Ganita Manjari, Class 9 Maths, Part II, is “The World of Algorithms.” It introduces algorithms through addition, divisor lists, GCD calculations, data structures and methods for improving efficiency. Teachoo helps you understand each procedure and the reasoning behind it.
2. What is an algorithm in Class 9 Maths?
An algorithm is a systematic, step-by-step procedure for solving a problem. Its instructions should be precise enough to follow without guessing what to do next.
Column addition, listing divisors and calculating the HCF using repeated division are examples of mathematical algorithms.
3. Do I need coding knowledge to study this chapter?
No. The chapter introduces algorithms through mathematical procedures written in words and arithmetic steps. You can execute them by hand.
Teachoo helps you begin with familiar calculations and develop the ability to describe, test and improve a procedure.
4. What does it mean to execute an algorithm?
To execute an algorithm means to follow its instructions step by step, updating the relevant values or lists as you proceed.
For example, while finding the divisors of 18, you check each candidate number and add it to the list only when it divides 18 exactly.
5. Why must an addition algorithm handle a column total of exactly 10?
A column total of exactly 10 requires writing 0 in that column and carrying 1 to the next column.
An instruction that only covers totals “less than 10” and “more than 10” leaves this case unspecified. A complete addition algorithm must cover totals greater than or equal to 10.
6. Are GCD and HCF the same?
Yes. Greatest common divisor (GCD) and highest common factor (HCF) refer to the same number: the largest positive integer that divides both given positive integers exactly.
For example, GCD(18, 24) = HCF(18, 24) = 6.
7. How can you find the GCD using divisor lists?
List the positive divisors of each number, identify the divisors appearing in both lists, and select the largest common divisor.
If the common-divisor list is arranged in increasing order, its last element is the GCD. If the list is not sorted, you must find its largest element explicitly.
8. What is a data structure in this chapter?
A data structure is a way of organising information used by an algorithm. This chapter uses lists to store divisors and common divisors.
Organising information clearly makes it easier to refer to intermediate results and carry out later steps correctly.
9. How does Euclid’s subtraction algorithm work?
For positive integers, repeatedly subtract the smaller number from the larger number. This preserves their GCD.
In the chapter’s formulation, the process eventually reaches a pair containing zero. The remaining non-zero number is the GCD. Teachoo helps you trace the changing pair and understand why the common divisors remain unchanged.
10. What is Āryabhaṭa’s division algorithm in Chapter 11?
The chapter presents a GCD algorithm that uses division remainders instead of repeated subtraction.
Divide the larger number by the smaller number, replace the pair with the smaller number and the remainder, and repeat. When the remainder becomes zero, the last non-zero divisor is the GCD.
The End-of-Chapter Exercises also refer to this as the improved version of Euclid’s algorithm.
11. What does “mod” mean?
m mod n is the remainder when m is divided by n, where n is non-zero.
For example:
17 mod 5 = 2, because 17 = 5 × 3 + 2.
This notation allows the remainder-based GCD algorithm to be written concisely.
12. Why does replacing a number with a remainder preserve the GCD?
If m = qn + r, any common divisor of m and n also divides r = m − qn.
Conversely, any common divisor of n and r also divides m = qn + r.
Therefore, the pairs (m, n) and (n, r) have the same common divisors and the same GCD.
13. Why is division more efficient than repeated subtraction?
One division can replace many subtraction steps.
For example, repeatedly subtracting 2 from 99 takes many steps. Division gives 99 = 2 × 49 + 1 immediately, reducing the GCD problem to GCD(2, 1). One further division completes the calculation.
14. Which exercises are included in Chapter 11?
The chapter includes Exercise Sets 11.1, 11.2 and 11.3, followed by five numbered End-of-Chapter Exercises. The final two end-of-chapter questions are starred and explore prime divisors and prime factorisation.
15. Why choose Teachoo for The World of Algorithms?
Choose Teachoo to understand how algorithms work, why their steps are valid and how they can be improved. Its focus on clear mathematical reasoning makes it a strong choice for studying Ganita Manjari Class 9 Chapter 11, practising GCD and HCF methods, and learning to write your own algorithms confidently.
Learn The World of Algorithms with Teachoo—follow the steps, understand the reasoning and discover better ways to solve problems.