NCERT Solutions for Class 9 Maths Ganita Manjari Chapter 11 The World of Algorithms

Class 9 Ganita Manjari Chapter 11 Quick Links:

• Exercise Set 11.1
• Exercise Set 11.2
• Exercise Set 11.3
• End of Chapter Exercises

• Download Class 9 Maths Offline App to study Class 9 Maths Ganita Manjari Offline.

The chapter also introduces Euclid’s Subtraction Algorithm and Aryabhata’s Division Algorithm, demonstrating how mathematical procedures can be improved to reduce the number of steps required. The NCERT Class 9 Maths Chapter 11 solutions provide detailed explanations of Exercise Sets 11.1, 11.2 and 11.3, along with the End-of-Chapter Exercises. These solutions help students develop mathematical reasoning, understand algorithm efficiency and apply systematic problem-solving techniques.

Answer:
Every digit has a place value. We add units to units, tens to tens, hundreds to hundreds, and so on.
If a column gives 10 or more, we regroup:
10 units = 1 ten.
10 tens = 1 hundred.
10 hundreds = 1 thousand.

We write the units digit of the column total and carry 1 to the next column on the left. We then add that carry along with the digits in the next column.
Example: 473 + 695
Units: 3 + 5 = 8. Write 8.
Tens: 7 + 9 = 16 tens = 1 hundred and 6 tens. Write 6 and carry 1.
Hundreds: 4 + 6 + 1 = 11 hundreds = 1 thousand and 1 hundred. Write 1 and carry 1.
Write the final carry in the thousands place.
Therefore, 473 + 695 = 1168.
Regrouping changes how we write the total, but it does not change its value. This is why the method works.

Answer:

1. Write the numbers one below the other with their decimal points in the same column.
2. Add zeros at the right end of the decimal part, if needed, so that both numbers have the same number of decimal places.
3. Treat missing digits on the left as 0.
4. Start with the rightmost digit and add each column, including any carry.
5. If the total is less than 10, write it and set the carry to 0.
6. If the total is 10 or more, write its units digit and carry 1 to the next column on the left.
7. Put the decimal point in the answer directly below the other decimal points. The decimal point itself is not a digit to be added.
8. If a carry remains after the leftmost column, write it on the left.

Example:
12.75
+ 03.60
───────
16.35

Hundredths: 5 + 0 = 5.
Tenths: 7 + 6 = 13. Write 3 and carry 1 to the units column.
Units: 2 + 3 + 1 = 6.
Tens: 1 + 0 = 1.
Therefore, 12.75 + 3.6 = 16.35.

Answer:
For each number n, start with an empty list [ ]. Check every integer j from 1 to n. Add j to the list only when it divides n exactly.

(a) Divisors of 15
Check j = 1, 2, 3, …, 15.
The list changes as follows:
j = 1: [1]
j = 3: [1, 3]
j = 5: [1, 3, 5]
j = 15: [1, 3, 5, 15]
For all other values of j, the list stays unchanged.
Therefore, divisors(15) = [1, 3, 5, 15].
Number of divisibility checks = 15.

(b) Divisors of 135
Check j = 1, 2, 3, …, 135.
The list changes as follows:
j = 1: [1]
j = 3: [1, 3]
j = 5: [1, 3, 5]
j = 9: [1, 3, 5, 9]
j = 15: [1, 3, 5, 9, 15]
j = 27: [1, 3, 5, 9, 15, 27]
j = 45: [1, 3, 5, 9, 15, 27, 45]
j = 135: [1, 3, 5, 9, 15, 27, 45, 135]
For all other values of j, the list stays unchanged.
Therefore, divisors(135) = [1, 3, 5, 9, 15, 27, 45, 135].
Number of divisibility checks = 135.

(c) Divisors of 775
Check j = 1, 2, 3, …, 775.
The list changes as follows:
j = 1: [1]
j = 5: [1, 5]
j = 25: [1, 5, 25]
j = 31: [1, 5, 25, 31]
j = 155: [1, 5, 25, 31, 155]
j = 775: [1, 5, 25, 31, 155, 775]
For all other values of j, the list stays unchanged.
Therefore, divisors(775) = [1, 5, 25, 31, 155, 775].
Number of divisibility checks = 775.

As n increases, this algorithm checks more possible divisors. It makes n divisibility checks for the number n. For example, 135 requires 9 times as many checks as 15.
A larger number need not have more divisors: 135 has 8 divisors, but 775 has only 6. The work increases because we check more numbers, not because we necessarily find more divisors.

Class 9 Maths Ganita Manjari Chapter 11 Exercise Set 11.1 Solutions

Answer:
The printed steps work for some pairs, but they do not cover every possible column total.
Example where the steps work: 2468 + 1357.
Units: 8 + 7 = 15. Write 5 and carry 1.
Tens: 6 + 5 + 1 = 12. Write 2 and carry 1.
Hundreds: 4 + 3 + 1 = 8. Write 8 and set the carry to 0.
Thousands: 2 + 1 + 0 = 3. Write 3 and set the carry to 0.

2468
+ 1357
──────
3825

Therefore, the answer is 3825.

Example showing the missing instruction: 4586 + 3414.
In the units column, 6 + 4 = 10.
The printed algorithm gives one instruction for a sum less than 10 and another for a sum more than 10. It does not say what to do when the sum is exactly 10.
So, if I follow only the written instructions, I cannot complete this addition.

Correction: In Steps 2 and 3, replace “more than 10” with “10 or more”. For a total of 10, write 0 and carry 1.
With this correction, 4586 + 3414 = 8000.

Answer:
The printed steps say to add two digits in each column, but they do not say what to do when one number has no digit in a column.
Example: 12345 + 321.
After adding the units, tens and hundreds columns, the 3-digit number has no digits left. The thousands and ten-thousands columns contain only one written digit each.

We must add an instruction: Treat each missing digit on the left as 0.
Thus, write 321 as 00321 for the addition:

12345
+ 00321
───────
12666

Therefore, 12345 + 321 = 12666.
So, the method works after the missing-digit instruction is added. We must also use the “10 or more” correction from Question 1 whenever needed.

Answer:
The rightmost digit of a whole number is its units digit. Aligning the numbers from the right puts units below units, tens below tens, hundreds below hundreds, and so on.
For example, in 12345 + 321, the 1 of 321 must be below the 5 of 12345 because both are units digits.

If we align incorrectly, we may add digits of different place values and get a wrong answer.

Answer:
We are adding only two numbers. The largest digit is 9, and the carry coming from the previous column is at most 1.
The largest possible total is:
9 + 9 + 1 = 19.

For any total from 10 to 19, the tens digit is 1. Therefore, the carry can only be 0 or 1.
In the first column, the largest total is 9 + 9 = 18, so the first carry is also at most 1.

Answer:
Step 5 writes the final carry on the left of the answer. If we leave it out, the answer is correct only when there is no final carry.

Example where it works:
1234 + 4321 = 5555.
There is no final carry, so leaving out Step 5 does not change the answer.

Example where it fails:
9999 + 9999 = 19998.
The column calculations write 9998 and leave a final carry of 1.
Without Step 5, we would report 9998 instead of 19998.
Therefore, Step 5 is needed whenever the leftmost column produces a carry.

Class 9 Maths Ganita Manjari Chapter 11 Exercise Set 11.2 Solutions

(i) Write an algorithm to find elements in List 1 that are not present in List 2.
Answer:
Algorithm:

1. Start with an empty list called result.
2. Take each number x in List 1, from left to right.
3. Check whether x occurs in List 2.
4. If x does not occur in List 2, add x at the end of result.
5. After checking every number in List 1, report result.

(ii) Write an algorithm to find elements in List 2 that are not present in List 1.
Answer:
Algorithm:

1. Start with an empty list called result.
2. Take each number x in List 2, from left to right.
3. Check whether x occurs in List 1.
4. If x does not occur in List 1, add x at the end of result.
5. After checking every number in List 2, report result.

Example for both parts:
List 1 = [1, 2, 3, 6]
List 2 = [1, 3, 5, 9]

Answer to (i): [2, 6]
Answer to (ii): [5, 9]
The output stays in increasing order because we check the original list from left to right.

Answer:
Let the positive integers be m and n.
Algorithm:

1. Make List A of the first n positive multiples of m:
   [m, 2m, 3m, …, nm].
2. Make List B of the first m positive multiples of n:
   [n, 2n, 3n, …, mn].
3. Check the entries of List A from left to right.
4. When an entry also occurs in List B, report it as the LCM and stop.

Why it works:
The lists are in increasing order, so the first common entry is the smallest positive common multiple.
The number mn occurs in both lists, so a common entry will definitely be found.

Example: Find lcm(4, 6).
List A = [4, 8, 12, 16, 20, 24].
List B = [6, 12, 18, 24].
The first common entry is 12.
Therefore, lcm(4, 6) = 12.

(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?
Answer:
We need to check only the positive integers j for which j² ≤ n.
In other words, check 1 up to the greatest whole number not exceeding √n.

Whenever j divides n, both j and n ÷ j are divisors.
If both numbers in a factor pair were greater than √n, their product would be greater than n. So, every factor pair has at least one member no greater than √n.

Example: n = 18.
Since 4² ≤ 18 < 5², check only 1, 2, 3 and 4.
1 gives the pair (1, 18).
2 gives the pair (2, 9).
3 gives the pair (3, 6).
4 does not divide 18.
So, only 4 possible divisors need to be checked instead of 18.
For a perfect square, do not enter the square root twice. For example, the pair (6, 6) for 36 contributes just one divisor, 6.

(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
Answer:
Not necessarily.
Writing both members of each pair as we find them does not give a list in increasing order. The original algorithm reports the rightmost common divisor, assuming that it is the greatest.

Example:
Paired list for 12 = [1, 12, 2, 6, 3, 4].
Paired list for 18 = [1, 18, 2, 9, 3, 6].

Checking the first list from left to right gives:
Common divisors = [1, 2, 6, 3].
The rightmost entry is 3, but gcd(12, 18) = 6.

Class 9 Maths Ganita Manjari Chapter 11 Exercise Set 11.3 Solutions

Answer:
The divisor lists would be in decreasing order.
Modified algorithm:

1. Find the divisors of m by checking m, m − 1, …, 1 and adding each divisor at the end of the list.
2. Similarly, find the divisors of n by checking n, n − 1, …, 1.
3. Start with an empty list called common-divisors.
4. Check the divisors of m in their listed order. If an entry also occurs in the list for n, add it to common-divisors.
5. Report the leftmost entry of common-divisors as the GCD.

Example:
Divisors of 12 in decreasing order = [12, 6, 4, 3, 2, 1].
Divisors of 18 in decreasing order = [18, 9, 6, 3, 2, 1].
Common divisors in decreasing order = [6, 3, 2, 1].
The leftmost entry is 6, so gcd(12, 18) = 6.
We could also stop as soon as we find the first common entry, because it is already the greatest.

Answer:
The first number that divides both m and n is their GCD. We can report it immediately and stop.

Algorithm:

1. Let k be the smaller of m and n.
2. If k divides both m and n, report k as the GCD and stop.
3. Otherwise, reduce k by 1 and return to Step 2.

Example: m = 12 and n = 18.
Check 12, 11, 10, 9, 8, 7 and then 6.
None of 12, 11, 10, 9, 8 or 7 divides both numbers.
6 divides both, so stop and report gcd(12, 18) = 6.

Class 9 Maths Ganita Manjari Chapter 11 End of Chapter Exercises Solutions

(i) gcd(375, 825)
(ii) gcd(51000, 81000)
(iii) gcd(1789287, 237656)
(iv) gcd(2587392, 157656)
Answer:
(i) gcd(375, 825)
Put the larger number first.
825 = 375 × 2 + 75.
375 = 75 × 5 + 0.
The last non-zero divisor is 75.
Therefore, gcd(375, 825) = 75.

(ii) gcd(51000, 81000)
81000 = 51000 × 1 + 30000.
51000 = 30000 × 1 + 21000.
30000 = 21000 × 1 + 9000.
21000 = 9000 × 2 + 3000.
9000 = 3000 × 3 + 0.
The last non-zero divisor is 3000.
Therefore, gcd(51000, 81000) = 3000.

(iii) gcd(1789287, 237656)
1789287 = 237656 × 7 + 125695.
237656 = 125695 × 1 + 111961.
125695 = 111961 × 1 + 13734.
111961 = 13734 × 8 + 2089.
13734 = 2089 × 6 + 1200.
2089 = 1200 × 1 + 889.
1200 = 889 × 1 + 311.
889 = 311 × 2 + 267.
311 = 267 × 1 + 44.
267 = 44 × 6 + 3.
44 = 3 × 14 + 2.
3 = 2 × 1 + 1.
2 = 1 × 2 + 0.
The last non-zero divisor is 1.
Therefore, gcd(1789287, 237656) = 1.

(iv) gcd(2587392, 157656)
2587392 = 157656 × 16 + 64896.
157656 = 64896 × 2 + 27864.
64896 = 27864 × 2 + 9168.
27864 = 9168 × 3 + 360.
9168 = 360 × 25 + 168.
360 = 168 × 2 + 24.
168 = 24 × 7 + 0.
The last non-zero divisor is 24.
Therefore, gcd(2587392, 157656) = 24.

Answer:
Here, m mod n means the remainder when m is divided by n.
For this division step, n must be greater than 0. If n = 0, the GCD algorithm stops without finding a remainder.
Let the remainder be r. Then:
m = qn + r, where 0 ≤ r < n.
Therefore, r = m − qn.

First direction:
Suppose d divides both m and n.
Write m = ad and n = bd for some integers a and b.
Then:
r = m − qn
= ad − qbd
= (a − qb)d.
So, d divides r. It already divides n.
Therefore, d divides both n and r.

Other direction:
Suppose d divides both n and r.
Write n = bd and r = cd for some integers b and c.
Then:
m = qn + r
= qbd + cd
= (qb + c)d.
So, d divides m. It already divides n.
Therefore, d divides both m and n.

Thus, the common divisors of m and n are exactly the common divisors of n and m mod n. Hence, their greatest common divisor is unchanged.

(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 distinct positive divisors: 1 and the number itself.

Algorithm prime(n):

1. If n < 2, report “not prime” and stop.
2. Use divisors(n) to find the list of positive divisors of n.
3. Count the entries in this list.
4. If there are exactly two entries, report “prime”.
5. Otherwise, report “not prime”.

Examples:
divisors(7) = [1, 7]. There are exactly two divisors, so 7 is prime.
divisors(9) = [1, 3, 9]. There are three divisors, so 9 is not prime.
1 is not prime because it has only one positive divisor.

(Hint: Compute divisors(n) and then filter out the primes in this list.)
Answer:
Algorithm primedivisors(n):

1. Use divisors(n) to find all the positive divisors of n.
2. Start with an empty list called prime-divisors.
3. Take each divisor d in the list, from left to right.
4. Use prime(d), from Question 3, to check whether d is prime.
5. If d is prime, add d to prime-divisors.
6. After checking every divisor, report prime-divisors.

Example: n = 180.
divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180].
The prime numbers in this list are 2, 3 and 5.
Therefore, primedivisors(180) = [2, 3, 5].

Each prime is listed only once here. This list does not yet say how many times each prime occurs in the prime factorisation.
For n = 1, the answer is the empty list [ ], since 1 has no prime divisors.

Answer:
Algorithm for prime factorisation:

1. Let the given positive integer be n. Set remaining = n.
2. Use primedivisors(n) to make the list of its prime divisors.
3. Start with an empty list called factorisation.
4. For each prime p in the prime-divisors list:
   (a) Set count = 0.
   (b) If p divides remaining, divide remaining by p and increase count by 1.
   (c) Repeat (b) until p no longer divides remaining.
   (d) Add the pair (p, count) to factorisation.
5. After processing all the prime divisors, report factorisation.

The first number in each pair is a prime factor. The second number tells us how many times it occurs.

Each division removes one occurrence of a prime factor. We count all occurrences of every prime divisor, so the list records the complete prime factorisation.
For n = 1, the list is empty because 1 has no prime factors.
Example: n = 180.
Prime divisors = [2, 3, 5].

For p = 2:
180 ÷ 2 = 90.
90 ÷ 2 = 45.
45 is not divisible by 2.
So, record (2, 2).

For p = 3:
45 ÷ 3 = 15.
15 ÷ 3 = 5.
5 is not divisible by 3.
So, record (3, 2).

For p = 5:
5 ÷ 5 = 1.
1 is not divisible by 5.
So, record (5, 1).

(i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this?
Answer:
Represent it as the list of pairs:
[(2, 2), (3, 2), (5, 1)].

(2, 2) means that 2 occurs twice.
(3, 2) means that 3 occurs twice.
(5, 1) means that 5 occurs once.
Multiplying these factors gives 2² × 3² × 5 = 180.

(ii) How would you compare the prime factorisations of two numbers?
Answer:
1. Find the prime factorisation lists of both numbers.
2. Find the prime factors that appear in both lists.
3. For each common prime, choose the smaller of its two powers.
4. Multiply these common prime powers. The product is the GCD.
5. If there is no common prime factor, the GCD is 1.

Example:
180 = 2² × 3² × 5.
252 = 2² × 3² × 7.

The common primes are 2 and 3.
The smaller power of 2 is 2.
The smaller power of 3 is 2.
Therefore:
gcd(180, 252) = 2² × 3² = 4 × 9 = 36.

To see why we use the smaller power, compare 12 = 2² × 3 and 18 = 2 × 3².
Their GCD can contain only one factor of 2 and one factor of 3, because those are the numbers of copies available in both.
So, gcd(12, 18) = 2 × 3 = 6.