Class 9 Maths Ganita Manjari Chapter 11 Solutions — The World of Algorithms

Sample test: try 4326 + 5784. The first column has $6+4=10$. The printed algorithm gives a branch for a sum less than 10 and a branch for a sum more than 10, but neither handles exactly 10. Therefore it cannot be followed to completion on this input. The intended second condition must be “10 or more”. With that repair the sum is 10110.

A case such as $1234+1111=2345$ works even with the printed wording because no column sum equals 10. One successful test does not establish that an algorithm always works.

A five-digit number and a three-digit number leave blank positions in the shorter row. The printed steps do not explicitly say how to add a digit to a blank. Repair this by padding the shorter number on the left with zeros, or by stating that missing digits count as zero. For example:

The rightmost digit is the units digit for every whole number. Right alignment places units under units, tens under tens and so on. Left-aligning unequal-length whole numbers would combine different place values. For decimals, align decimal points instead.

Two base-ten digits are at most 9 each and the incoming carry is at most 1. A total from 0 to 19 creates at most one new ten. Initially the carry is 0; this bound then continues to hold for every column. It is a statement about adding two numbers; adding many rows at once can produce a larger carry.

Without Step 5, the result loses its leading digit when the leftmost column generates a carry. For 8000 + 4000, the correct result is 12000; omitting the final carry leaves only 2000. For $1234+1111=2345$ there is no final carry, so omitting the step happens not to change the answer.

(i) Initialise an empty result. Visit each value in List 1 in order. If it does not occur in List 2, append it to the result. Report that result. (ii) Exchange the roles of List 1 and List 2 and repeat. If “elements” means distinct values and repeated values are allowed in the inputs, append a value only if it is not already in the result.

Example: List $1=[1,3,5,7]$ and List $2=[3,4,7,9]$ give [1, 5] in (i) and [4, 9] in (ii). These are different questions; neither result is a list of common elements.

Assume m and n are positive integers.

1. Let L be the larger of m and n.
2. Check L, 2L, 3L, … in that order.
3. At each candidate, test divisibility by both m and n. At the first common multiple, report it and stop.

The process stops no later than the product mn, which is a common multiple. Every common multiple is a multiple of L, and the candidates are visited in increasing order, so the first match is the least. For 6 and 8, candidates 8, 16 and 24 give $\mathrm{LCM}=24$.

Once a correct GCD algorithm is available, a faster alternative is:

Prime factorisation justifies the formula: for each prime, its exponents in the gcd and lcm are the smaller and larger exponents, whose sum is the sum of the two original exponents.

(i) Test the integers from 1 through $\lfloor\sqrt n\rfloor$. If j divides n, record j and $\frac nj$. If they are equal, record the common value only once. Every divisor above the square root has a partner below it, so no divisor is missed. For 18, only 1, 2, 3 and 4 need testing; for a square such as 36, include 6.

(ii) Pair-wise output need not be sorted. For 18 it might be [1, 18, 2, 9, 3, 6]. If all of these also divide the other number 36, taking the rightmost entry would wrongly give 6 instead of 18. Sort the common-divisor list before choosing its rightmost value, or explicitly take the largest value. The list order is part of the original algorithm’s justification.

Scanning from n down to 1 produces a decreasing divisor list. If both lists and the common-divisor scan follow this decreasing order, the largest common divisor is the first common entry, not the last. You may stop when that first match is found. If only the second membership-test list is reversed while the first is still scanned upwards, the common output retains the first list’s increasing order; its last entry remains the gcd. What matters is the order in which candidates are appended.

Start at the smaller of m and n and scan downwards. The first integer dividing both is their gcd, so report it immediately and stop. If you keep replacing the stored answer until reaching 1, you will end with 1 for every input and the algorithm will fail when the true gcd exceeds 1.

At each row divide the current first number by the second, then use the second number and the remainder as the next pair. The last nonzero divisor is the gcd.

(i) (375, 825)

Check: 75 divides both original numbers; the remainder chain proves that every common divisor divides this final nonzero value.

(ii) (51000, 81000)

Check: 3000 divides both original numbers; the remainder chain proves that every common divisor divides this final nonzero value.

(iii) (1789287, 237656)

Check: 1 divides both original numbers; the remainder chain proves that every common divisor divides this final nonzero value.

(iv) (2587392, 157656)

Check: 24 divides both original numbers; the remainder chain proves that every common divisor divides this final nonzero value.

Assume $m\ge n>0$ and let $m=qn+r$, where $r=m\bmod n$. Let d be a positive integer.

Forward: if d divides m and n, it divides $m-qn=r$. Thus it divides n and r. Reverse: if d divides n and r, it divides $qn+r=m$. Thus it divides m and n. The two pairs have exactly the same common divisors, so their greatest common divisors agree.

The condition $n>0$ is needed because “m mod 0” is undefined. When $n=0$, the algorithm stops before taking a remainder.

Divisor-list version, matching the hint:

1. Input an integer n. If n < 2, report “not prime” and stop.
2. Compute the list of positive divisors of n.
3. If the list contains exactly two values, report “prime”; otherwise report “not prime”.

For example, divisors$\left(13\right)=[1,13]$, so 13 is prime. Divisors$\left(1\right)=[1]$, so 1 is not prime. Divisors(12) has more than two values, so 12 is composite.

More efficient equivalent: test integers d from 2 while $d^2\le n$. If any divides n, report “not prime” immediately. If the loop ends with no divisor, report “prime”. A composite number has a factor at most its square root, which proves the test is sufficient.

Assume n is a positive integer.

1. Start an empty list P.
2. Compute divisors(n). For each divisor d, run prime(d).
3. If prime(d) reports true, append d to P.
4. Report P.

For $n=180$, the output is [2, 3, 5]. This lists the distinct prime divisors, not repeated prime factors. For $n=1$, the output is the empty list, since 1 has no prime divisor. Each listed item is both prime and a divisor; every such item appears in divisors(n), so none is missed.

Input: a positive integer n. The following trial-division algorithm records prime–exponent pairs.

1. Set remaining = n, $d=2$, and start an empty factor list.
2. While $d^2\le\text{remaining}$, set an exponent counter e to 0. Repeatedly divide remaining by d for as long as the remainder is zero, increasing e by 1 each time.
3. If $e>0$, append the pair (d, e). Increase d by 1 and repeat Step 2.
4. When the loop ends, if remaining > 1, append (remaining, 1). Report the factor list.

Previously tested prime factors have been fully removed, so any later d that actually divides the remaining number must be prime. Once $d^{2}$ exceeds the remaining number, a remaining value greater than 1 cannot be composite without having a smaller factor already removed. The procedure terminates because trial divisors increase and successful divisions decrease the remaining value.

(i) For 180, use [(2, 2), (3, 2), (5, 1)], where each pair means (prime, exponent):

(ii) Compare the exponents of the same primes, treating a missing prime as exponent zero. For the gcd, take the smaller exponent of each common prime. For the lcm, take the larger exponent of every prime appearing in either number. For example:

For $n=1$, the factor list is empty and its product is understood as 1. Zero has no finite prime factorisation and is outside this algorithm’s stated input domain.