NCERT Solutions · Class 9 Mathematics The World of Algorithms

(i) Write List $\displaystyle 2$ as \(\displaystyle b_1<b_2<\cdots\).1. Start with an empty list-only-in-$\displaystyle 1$ and \(\displaystyle j=1\). 2. For each \(\displaystyle a\) in List $\displaystyle 1$, in order: Example:\[\text{List 1}=[2,4,6,8,10],\qquad \text{List 2}=[4,5,6,9,10,12] \]\[\begin{array}{c|c|l} a & b_j & \text{action}\\ \hline 2 & 4 & 4>2:\ \text{add } 2\\ 4 & 4 & \text{equal}\\ 6 & 6 & \text{equal}\\ 8 & 9 & 9>8:\ \text{add } 8\\ 10 & 10 & \text{equal} \end{array} \]\[\text{list-only-in-1}=[2,8] \](ii) Interchange the two lists in the steps above. For the same example:\[\text{list-only-in-2}=[5,9,12] \]Answer: (i) for each \(\displaystyle a\) in List $\displaystyle 1$, move \(\displaystyle j\) forward in List $\displaystyle 2$ and keep \(\displaystyle a\) if \(\displaystyle b_j>a\) or List $\displaystyle 2$ is used up; example \(\displaystyle [2,8]\). (ii) the same with the lists interchanged; example \(\displaystyle [5,9,12]\).

Any common multiple is a multiple of the larger number, so scan its multiples.1. Let \(\displaystyle a=\max(m,n)\) and \(\displaystyle b=\min(m,n)\). 2. For each \(\displaystyle k=1,2,\ldots,b\): if \(\displaystyle b\) divides \(\displaystyle ka\), report \(\displaystyle ka\) and stop.It always stops, since \(\displaystyle k=b\) gives \(\displaystyle ba=mn\), a common multiple. For \(\displaystyle m=12,\ n=18\):\[a=18,\ b=12:\qquad 18\bmod 12=6\neq 0,\qquad 36\bmod 12=0 \]\[\operatorname{lcm}(12,18)=36 \]Faster, using Āryabhaṭa's algorithm for the gcd:\[\gcd(18,12)=\gcd(12,6)=\gcd(6,0)=6 \]\[\operatorname{lcm}(m,n)=\frac{mn}{\gcd(m,n)}=\frac{12\times 18}{6}=36 \]Answer: check \(\displaystyle a,2a,3a,\ldots\) (\(\displaystyle a=\max(m,n)\)) until \(\displaystyle \min(m,n)\) divides one, or use \(\displaystyle \operatorname{lcm}(m,n)=\dfrac{mn}{\gcd(m,n)}\); for example \(\displaystyle \operatorname{lcm}(12,18)=36\).

(i) If \(\displaystyle d\) divides \(\displaystyle n\), so does \(\displaystyle n/d\), and \(\displaystyle d\cdot\frac{n}{d}=n\), so they cannot both exceed \(\displaystyle \sqrt n\). Examine only\[j=1,2,\ldots,\lfloor\sqrt n\rfloor \]Each \(\displaystyle j\) dividing \(\displaystyle n\) gives the pair \(\displaystyle (j,\,n/j)\); if \(\displaystyle j^2=n\), list \(\displaystyle j\) once.\[n=18:\quad \lfloor\sqrt{18}\rfloor=4,\quad j=1,2,3\ \text{give}\ (1,18),(2,9),(3,6),\quad j=4\ \text{fails} \](ii) No, not as described. Step $\displaystyle 5$ takes the rightmost common divisor as the largest, which needs an increasing list. Pair order is not increasing:\[\text{divisors of }18\text{ in pair order}:\quad [1,18,2,9,3,6] \]\[\text{all divide }36,\ \text{so the rightmost is }6,\ \text{but }\gcd(18,36)=18 \]Fix: sort the list, or report the largest common divisor.Answer: (i) \(\displaystyle \lfloor\sqrt n\rfloor\) numbers, \(\displaystyle 1\) to \(\displaystyle \lfloor\sqrt n\rfloor\). (ii) Not as described, since pair order is not increasing; sort the list first.