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

The Class 9 Maths Ganita Manjari Chapter 11 End of Chapter Exercises Solutions – The World of Algorithms help students revise and apply the key concepts covered throughout the chapter. These exercises include questions based on algorithms, divisors, GCD, prime numbers, prime factorisation, and step-by-step problem-solving methods.

The solutions are presented in a clear and systematic manner to strengthen students’ understanding of logical reasoning and algorithmic thinking. Students can also access the Class 9 Maths Ganita Manjari Chapter 11 End of Chapter Exercises Solutions PDF for quick revision and convenient offline study.

NCERT Class 9 Maths Ganita Manjari Chapter 11 End-of-Chapter Exercises

Solution:

Assume m ≥ n, and let

m = qn + r,

where r = m mod n.

We need to show that:

d divides both m and n if and only if d divides both n and m mod n.

Forward direction:

Suppose d divides both m and n.

Then there exist integers a and b such that:

m = ad
n = bd

Since

r = m − qn,

we get:

r = ad − qbd
r = d(a − qb)

Therefore, d divides r = m mod n.

Hence, if d divides m and n, then d divides both n and m mod n.

Reverse direction:

Now suppose d divides both n and r, where r = m mod n.

Then:

n = bd
r = cd

for some integers b and c.

Since

m = qn + r,

we get:

m = qbd + cd
m = d(qb + c)

Therefore, d divides m.

Hence, if d divides both n and m mod n, then d divides both m and n.

Therefore,

d divides m and n if and only if d divides both n and m mod n.

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 number of divisors in the list.
4. If there are exactly two divisors, 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.

Also, 1 is not prime because it has only one positive divisor.

4. Write an algorithm prime divisors(n) to compute the list of divisors of n that are prime numbers.

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, one at a time.
4. Use prime(d) to check whether d is a prime number.
5. If d is prime, add d to prime-divisors.
6. After checking all the divisors, report prime-divisors.

Example: Let n = 180.

divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

The prime divisors in this list are 2, 3 and 5.

Therefore,

primedivisors(180) = [2, 3, 5]

Each prime divisor is listed only once. This list gives the prime numbers that divide n; it does not indicate how many times each prime occurs in the prime factorisation.

For n = 1,

primedivisors(1) = [ ]

because 1 has no prime divisors.

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.

Answer:

Algorithm for prime factorisation:

1. Let the given positive integer be n. Set remaining = n.
2. Use primedivisors(n) to find the list of prime divisors of n.
3. Start with an empty list called factorisation.
4. For each prime p in the list of prime divisors:
   • Set count = 0.
   • While p divides remaining, divide remaining by p and increase count by 1.
   • Add the pair (p, count) to factorisation.
5. After all the prime divisors have been processed, report factorisation.

The first number in each pair is a prime factor, and the second number tells us how many times that prime occurs.

For n = 1, the factorisation list is empty because 1 has no prime factors.

Example: n = 180

Prime divisors of 180 = [2, 3, 5]

For p = 2:

180 ÷ 2 = 90
90 ÷ 2 = 45

So, record (2, 2).

For p = 3:

45 ÷ 3 = 15
15 ÷ 3 = 5

So, record (3, 2).

For p = 5:

5 ÷ 5 = 1

So, record (5, 1).

Therefore,

factorisation = [(2, 2), (3, 2), (5, 1)]

and

180 = 2² × 3² × 5.

(i) The prime factorisation of 180 is 2² × 3² × 5¹. How would you represent this?

Represent it as:

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

Here, each pair gives the prime factor and the number of times it occurs.

(ii) How would you compare the prime factorisations of two numbers?

1. Find the prime factorisation of both numbers.
2. Identify the prime factors common to both.
3. For each common prime, take the smaller of its two powers.
4. Multiply these common prime powers.
5. The product is the GCD.

For example:

180 = 2² × 3² × 5
252 = 2² × 3² × 7

The common prime factors are 2 and 3.

Therefore,

gcd(180, 252) = 2² × 3² = 36.

If there is no common prime factor, the GCD is 1.

Related Links:

• NCERT Solutions for Class 9 Maths Ganita Manjari Chapter 11 
• NCERT Solutions for Class 9 Maths Ganita Manjari Chapter 11 Exercise 11.1
• NCERT Solutions for Class 9 Maths Ganita Manjari Chapter 11 Exercise 11.2
• NCERT Solutions for Class 9 Maths Ganita Manjari Chapter 11 Exercise 11.3