NCERT Solutions for Class 9 Maths Chapter 11 — End-of-Chapter Exercises#

∴ gcd(375, 825) = 75.

∴ gcd(51000, 81000) = 3000.

∴ gcd(1789287, 237656) = 1 — the two numbers have no common factor other than 1.

∴ gcd(2587392, 157656) = 24.

Divide $m$ by $n$: $m = qn + r$, where $q$ is the quotient and $r = m \bmod n$ is the remainder.

If $d$ divides $m$ and $n$: write $m = ad$ and $n = bd$. Then:

So $d$ divides $r = m \bmod n$ (and of course $d$ divides $n$).

If $d$ divides $n$ and $r$: write $n = xd$ and $r = yd$. Then:

So $d$ divides $m$ (and $n$).

∴ $d$ divides both $m$ and $n$ if and only if it divides both $n$ and $m \bmod n$. The two pairs have exactly the same common divisors, so $\text{gcd}(m, n) = \text{gcd}(n, m \bmod n)$. This justifies Step 3 of the algorithm.

1. Let list-of-divisors be the list obtained by computing divisors(n).
2. If list-of-divisors has exactly 2 elements, report “n is prime”.
3. Otherwise, report “n is not prime”.

Why it works: a prime has exactly two divisors, 1 and itself. The number 1 has only one divisor, and a composite number has three or more — so both are correctly reported as not prime.

Examples: divisors(13) = [1, 13] → prime. divisors(15) = [1, 3, 5, 15] → not prime. divisors(1) = [1] → not prime.

(Faster version: check $j$ from 2 up to $\sqrt{n}$; if any $j$ divides $n$, report “not prime”; if none does and $n > 1$, report “prime”.)

1. Let list-of-divisors be the list obtained by computing divisors(n).
2. Start with an empty list prime-divisors.
3. For each number $d$ in list-of-divisors:
   • if prime(d) reports “d is prime”, add $d$ to prime-divisors.
4. Report prime-divisors.

Example: divisors(60) = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]. Keeping only the primes gives primedivisors(60) = [2, 3, 5].

1. Let primes be the list obtained by computing primedivisors(n).
2. Start with an empty list factorisation, and let $r = n$.
3. For each prime $p$ in primes:
   • set count to 0;
   • while $p$ divides $r$: divide $r$ by $p$ and add 1 to count;
   • add the pair (p, count) to factorisation.
4. Report factorisation.

Example: $n = 180$. primedivisors(180) = [2, 3, 5]. Dividing 180 by 2 twice gives 45 (count 2); 45 by 3 twice gives 5 (count 2); 5 by 5 once gives 1 (count 1). So factorisation = [(2, 2), (3, 2), (5, 1)].

As a list of pairs (prime, power), with the primes in increasing order:

Each pair says which prime appears and how many times.

To find the gcd, go through the primes that appear in both lists; for each such prime, take the smaller of its two powers. Multiply these together. (Primes that appear in only one list do not contribute.)

Example: $180 = [(2, 2), (3, 2), (5, 1)]$ and $168 = [(2, 3), (3, 1), (7, 1)]$. The common primes are 2 and 3, with smaller powers 2 and 1:

(Taking the larger power of every prime that appears in either list gives the lcm instead.) Because both lists are in increasing order of primes, they can be compared by walking through them together, as in Exercise Set 11.2, Question 1.