NCERT Solutions · Class 9 Mathematics The World of Algorithms

Reverse the pair if \(\displaystyle m<n \); then replace \(\displaystyle (m,n) \) by \(\displaystyle (n,\, m \bmod n) \) until \(\displaystyle n=0 \); the answer is \(\displaystyle m \).(i)\[\gcd(375,825)=\gcd(825,375)=\gcd(375,75)=\gcd(75,0)=75 \](ii)\[\gcd(51000,81000)=\gcd(81000,51000)=\gcd(51000,30000)=\gcd(30000,21000) \]\[=\gcd(21000,9000)=\gcd(9000,3000)=\gcd(3000,0)=3000 \](iii) Successive pairs:\[\begin{array}{r|r|r} m & n & m \bmod n \\ \hline 1789287 & 237656 & 125695 \\ 237656 & 125695 & 111961 \\ 125695 & 111961 & 13734 \\ 111961 & 13734 & 2089 \\ 13734 & 2089 & 1200 \\ 2089 & 1200 & 889 \\ 1200 & 889 & 311 \\ 889 & 311 & 267 \\ 311 & 267 & 44 \\ 267 & 44 & 3 \\ 44 & 3 & 2 \\ 3 & 2 & 1 \\ 2 & 1 & 0 \\ 1 & 0 & - \end{array} \]\[\gcd(1789287,237656)=1 \](iv) Successive pairs:\[\begin{array}{r|r|r} m & n & m \bmod n \\ \hline 2587392 & 157656 & 64896 \\ 157656 & 64896 & 27864 \\ 64896 & 27864 & 9168 \\ 27864 & 9168 & 360 \\ 9168 & 360 & 168 \\ 360 & 168 & 24 \\ 168 & 24 & 0 \\ 24 & 0 & - \end{array} \]\[\gcd(2587392,157656)=24 \]Answer: (i) \(\displaystyle 75 \); (ii) \(\displaystyle 3000 \); (iii) \(\displaystyle 1 \); (iv) \(\displaystyle 24 \)

Write \(\displaystyle m = qn + r \) with \(\displaystyle r = m \bmod n \).If \(\displaystyle d \) divides \(\displaystyle m \) and \(\displaystyle n \):\[m = ad, \quad n = bd \]\[r = m - qn = ad - qbd = (a-qb)\,d \]so \(\displaystyle d \) divides \(\displaystyle n \) and \(\displaystyle r \).Converse: if \(\displaystyle d \) divides \(\displaystyle n \) and \(\displaystyle r \), then \(\displaystyle d \) divides \(\displaystyle m \) and \(\displaystyle n \). True.\[n = xd, \quad r = yd \]\[m = qn + r = qxd + yd = (qx+y)\,d \]Answer: \(\displaystyle d \mid m,\ d \mid n \iff d \mid n,\ d \mid (m \bmod n) \), both directions verified

Algorithm prime(n):1. Compute the list divisors(n).2. Count the entries in this list.3. If the count is exactly $\displaystyle 2$, report "prime"; otherwise report "not prime".A prime has exactly the two divisors $\displaystyle 1$ and \(\displaystyle p \); the number $\displaystyle 1$ has only one.\[\text{divisors}(13)=[1,13], \quad 2 \text{ entries: prime} \]\[\text{divisors}(18)=[1,2,3,6,9,18], \quad 6 \text{ entries: not prime} \]\[\text{divisors}(1)=[1], \quad 1 \text{ entry: not prime} \]Other correct algorithms are equally valid.Answer: prime(n) reports "prime" exactly when divisors(n) has $\displaystyle 2$ entries

Algorithm primedivisors(n):1. Let list-of-divisors be divisors(n).2. Start with an empty list prime-divisors.3. For each d in list-of-divisors, if prime(d) reports "prime", add d to prime-divisors.4. Report prime-divisors.\[\text{divisors}(18)=[1,2,3,6,9,18] \]\[\text{prime}(d) \text{ holds for } d=2,3 \text{ only} \]\[\text{primedivisors}(18)=[2,3] \]Other correct algorithms are equally valid.Answer: primedivisors(n) keeps the d in divisors(n) for which prime(d) holds; e.g. \(\displaystyle \text{primedivisors}(18)=[2,3] \)

Algorithm factorise(n):1. Let primes be primedivisors(n); set t = n; start with an empty list factorisation.2. For each p in primes: set e = $\displaystyle 0$; while p divides t, replace t by t/p and increase e by $\displaystyle 1$; add (p, e) to factorisation.3. Report factorisation.\[\text{primedivisors}(180)=[2,3,5] \]\[180 \to 90 \to 45 \ (e=2), \quad 45 \to 15 \to 5 \ (e=2), \quad 5 \to 1 \ (e=1) \](i) Pairs (prime, exponent), primes increasing; a list like \(\displaystyle [2,2,3,3,5] \) is also valid.\[2^2\times 3^2\times 5^1 \ \longrightarrow \ [(2,2),(3,2),(5,1)] \](ii) Compare prime by prime; for the gcd take the smaller exponent ($\displaystyle 0$ if the prime is absent).\[150 = 2^1\times 3^1\times 5^2 \ \longrightarrow \ [(2,1),(3,1),(5,2)] \]\[\gcd(180,150) = 2^{\min(2,1)}\times 3^{\min(2,1)}\times 5^{\min(1,2)} = 2\times 3\times 5 = 30 \]Answer: (i) \(\displaystyle [(2,2),(3,2),(5,1)] \); (ii) smaller exponent of each prime gives the gcd