SolveNCERT
SolveNCERT
HomeSolutionsMathsCh 11End-of-Chapter Exercises
Class 9 · MathsNCERT 2026 Revised Syllabus

Chapter 11: The World of Algorithms (0904CH11)

End-of-Chapter Exercises — 5 questions with step-by-step notebook-style answers.

End-of-Chapter Exercises(5 questions)

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)

School Level Solution

(i) 825=2(375)+75; 375=5(75)+0, so gcd=75.(ii) 81000=1(51000)+30000; 51000=1(30000)+21000; 30000=1(21000)+9000; 21000=2(9000)+3000; 9000=3(3000)+0. Hence gcd=3000.(iii) Euclid’s algorithm gives successive remainders until the final non-zero remainder is 1, so gcd=1 (the numbers are coprime).(iv) The successive remainders terminate at 24, with the next remainder 0, so gcd=24.
2
Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.

School Level Solution

Proof. Write m=qn+r, where r=m mod n.(⇒) If d|m and d|n, then d divides m−qn=r. Hence d|n and d|r.(⇐) If d|n and d|r, then d divides qn+r=m. Hence d|m and d|n.Both directions hold, so the two pairs have exactly the same common divisors; in particular, their gcds are equal.
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)?)

School Level Solution

```text prime(n): if n < 2: return false D := divisors(n) if length(D) = 2: return true else: return false ``` A prime integer has exactly two positive divisors, 1 and itself. A number below 2 is not prime. Hence the test correctly distinguishes primes from composites.
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.)

School Level Solution

```text primedivisors(n): D := divisors(n) P := empty list for each d in D: if prime(d): append d to P return P ``` For example, divisors(180) = [1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180], so primedivisors(180) = [2,3,5]. The algorithm checks every divisor and keeps precisely the prime ones.
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?

School Level Solution

```text primeFactorisation(n): F := empty list of (prime, exponent) pairs p := 2 while p*p <= n: e := 0 while n mod p = 0: n := n / p e := e + 1 if e > 0: append (p,e) to F p := p + 1 if n > 1: append (n,1) to F return F ```(i) Store 180=2²×3²×5 as [(2,2),(3,2),(5,1)], meaning prime 2 has exponent 2, prime 3 exponent 2 and prime 5 exponent 1.(ii) For two numbers, compare the exponents of each prime, treating a missing prime as exponent 0. The gcd uses the minimum exponent for each prime; the lcm uses the maximum exponent. If every exponent in one factorisation is no larger than the corresponding exponent in the other, the first number divides the second.

Other Chapters