NCERT Solutions Class 9 Maths Ch 11: The World of Algorithms

Regrouping 10 units as 1 ten, 10 tens as 1 hundred, and so on changes how we write the total but not its value.

1. Place valuesEvery digit has a place value. We add units to units, tens to tens, hundreds to hundreds, and so on, because only things of the same kind can be added together.
2. RegroupingIf a column total is 10 or more, we regroup: 10 units = 1 ten, 10 tens = 1 hundred, 10 hundreds = 1 thousand. We write the units digit of the column total and carry 1 to the next column on the left.
3. Example: 473 + 695

   Column	Digits added	Carry in	Total	Write	Carry out
   Units	3 + 5	0	8	8	0
   Tens	7 + 9	0	16	6	1
   Hundreds	4 + 6	1	11	1	1
   Thousands	(none)	1	1	1	0

   473 + 695 = 1168
4. Why it is correctThe carry is just the “10 units = 1 ten” exchange written down. Exchanging 10 of one kind for 1 of the next kind never changes the total value, so the final answer is right.

Line up the decimal points, pad with zeros so both numbers have the same number of decimal places, and then add as before.

1. The modified steps
   1. Write the numbers one below the other with their decimal points in the same column.
   2. Add zeros at the right end of the decimal part, if needed, so that both numbers have the same number of decimal places.
   3. Treat missing digits on the left as 0.
   4. Start from the rightmost digit and add each column, including the carry (carry 1 if the total is 10 or more, otherwise 0).
   5. Put the decimal point in the answer directly below the other decimal points (it is not a digit to be added).
   6. If a carry remains after the leftmost column, write it at the left.
2. Example: 12.75 + 3.6Write 3.6 as 3.60 and add.

   Column	Digits added	Carry in	Total	Write	Carry out
   Hundredths	5 + 0	0	5	5	0
   Tenths	7 + 6	0	13	3	1
   Units	2 + 3	1	6	6	0
   Tens	1 + 0	0	1	1	0

   12.75 + 3.6 = 16.35

Divisors of 15: 1, 3, 5, 15. Of 135: 1, 3, 5, 9, 15, 27, 45, 135. Of 775: 1, 5, 25, 31, 155, 775. The number of checks equals n.

1. The algorithmStart with an empty list. Check every whole number j from 1 to n. Add j to the list only when j divides n exactly.
2. The results

   n	Divisors found	Number of checks
   15	1, 3, 5, 15	15
   135	1, 3, 5, 9, 15, 27, 45, 135	135
   775	1, 5, 25, 31, 155, 775	775

3. How the work growsThe algorithm makes n checks for the number n, so the work grows in proportion to n. For example, 135 needs 9 times as many checks as 15. A larger number need not have more divisors (135 has 8 divisors, 775 has only 6): the work increases because more numbers are checked, not because more divisors are found.

It works for most pairs (such as 2468 + 1357 = 3825), but it fails when a column total is exactly 10 (such as 4586 + 3414), because the steps do not say what to do then.

1. A pair where the steps work: 2468 + 1357

   Column	Digits added	Carry in	Total	Write	Carry out
   Units	8 + 7	0	15	5	1
   Tens	6 + 5	1	12	2	1
   Hundreds	4 + 3	1	8	8	0
   Thousands	2 + 1	0	3	3	0

   2468 + 1357 = 3825
2. A pair where they fail: 4586 + 3414In the units column, 6 + 4 = 10. One instruction covers totals less than 10 and the other covers totals more than 10. A total of exactly 10 is not covered, so following only the written steps we cannot go on.
3. The fixChange “more than 10” to “10 or more”. For a total of 10, write 0 and carry 1. Then 4586 + 3414 = 8000.

Not as written. We must add the instruction “treat each missing digit on the left as 0”. Then 12345 + 321 = 12666.

1. The problemAfter the units, tens and hundreds columns, the 3-digit number has no digits left, so the steps do not tell us what to add in the thousands and ten-thousands columns.
2. The fixWrite 321 as 00321, that is, treat each missing digit on the left as 0.

   Column	Digits added	Carry in	Total	Write	Carry out
   Units	5 + 1	0	6	6	0
   Tens	4 + 2	0	6	6	0
   Hundreds	3 + 3	0	6	6	0
   Thousands	2 + 0	0	2	2	0
   Ten-thousands	1 + 0	0	1	1	0

   12345 + 321 = 12666

So that digits of the same place value are added together.

1. Place valueThe rightmost digit of a whole number is its units digit. Aligning from the right puts units under units, tens under tens, hundreds under hundreds, and so on.
2. ExampleIn 12345 + 321, the 1 of 321 is a units digit, so it goes below the 5 of 12345 (units); the 2 goes below the 4 (tens), and the 3 below the 3 (hundreds). If we aligned from the left instead, the 3 of 321 would sit below the 1 of 12345 (ten-thousands), and we would be adding digits of different place values and get a wrong answer.

Because the largest possible column total is 9 + 9 + 1 = 19.

1. Largest totalWe add only two digits (each at most 9) and a carry coming from the previous column (at most 1): 9 + 9 + 1 = 19.
2. The tens digitEvery total from 10 to 19 has tens digit 1, so the carry is 0 or 1.
3. The first columnIn the first column there is no carry in; the largest total is 9 + 9 = 18, so the first carry is also at most 1.

Without Step 5 the answer is wrong whenever the leftmost column produces a carry.

1. Step 5Step 5 writes the final carry at the left of the answer. Without it the answer is right only when there is no final carry.
2. Where it works1234 + 4321 = 5555. There is no carry out of the leftmost column, so leaving out Step 5 changes nothing.
3. Where it fails9999 + 9999 = 19998. The columns give 9998 and a final carry of 1. Without Step 5 we would report 9998 instead of 19998.

Check each element of one list against the other, and keep the ones that do not occur there.

1. (i) Elements of List 1 not in List 2
   1. Start with an empty list called result.
   2. Take each number x in List 1, from left to right.
   3. Check whether x occurs in List 2.
   4. If x does not occur in List 2, add x at the end of result.
   5. After every number of List 1 has been checked, report result.
2. (ii) Elements of List 2 not in List 1The same algorithm with the two lists exchanged: take each x in List 2, check whether it occurs in List 1, and add it to result if it does not.
3. ExampleList 1 = [1, 2, 3, 6] and List 2 = [1, 3, 5, 9]. Answer to (i): [2, 6]. Answer to (ii): [5, 9]. The output is in increasing order because we go through the original list from left to right.

List multiples of both numbers and report the first one that appears in both lists.

1. Algorithm
   1. Make List A of the first n positive multiples of m: [m, 2m, 3m, …, nm].
   2. Make List B of the first m positive multiples of n: [n, 2n, 3n, …, mn].
   3. Check the entries of List A from left to right.
   4. When an entry also occurs in List B, report it as the LCM and stop.
2. Why it worksBoth lists are in increasing order, so the first common entry is the smallest common multiple. The number mn is in both lists, so a common entry is always found.
3. Example: lcm(4, 6)List A = [4, 8, 12, 16, 20, 24] and List B = [6, 12, 18, 24]. The first common entry is 12, so lcm(4, 6) = 12.

Only the numbers from 1 up to √n (the greatest whole number not exceeding √n).

1. WhyWhenever j divides n, both j and n ÷ j are divisors. If both numbers of a pair were greater than √n, their product would be greater than n. So every pair has at least one number that is at most √n.
2. Example: n = 18Since 4² = 16 ≤ 18 < 25 = 5², we check only 1, 2, 3 and 4: 1 gives the pair (1, 18), 2 gives (2, 9), 3 gives (3, 6), and 4 does not divide 18. Only 4 checks instead of 18.
3. A perfect squareFor n = 36 the pair is (6, 6); count the divisor 6 only once.

Not necessarily. The paired list is not in increasing order, so the last common divisor is not always the greatest.

1. The original algorithmIt lists the divisors in increasing order, finds the common divisors, and reports the rightmost one as the greatest.
2. A counter-examplePaired list for 12 = [1, 12, 2, 6, 3, 4]. Paired list for 18 = [1, 18, 2, 9, 3, 6]. Going through the first list from left to right, the common divisors are [1, 2, 6, 3].
3. The problemThe rightmost entry is 3, but gcd(12, 18) = 6. So we must report the largest common divisor (not the last one), or sort the list first.

The divisor lists come out in decreasing order, and the first common divisor is the gcd.

1. Modified algorithm
   1. Find the divisors of m by checking m, m − 1, …, 1, adding each divisor at the end of the list.
   2. Find the divisors of n in the same way, checking n, n − 1, …, 1.
   3. Check the divisors of m in their listed order. If an entry also occurs in the list for n, add it to common-divisors.
   4. Report the leftmost entry of common-divisors as the gcd.
2. ExampleDivisors of 12 in decreasing order = [12, 6, 4, 3, 2, 1]. Divisors of 18 = [18, 9, 6, 3, 2, 1]. Common divisors = [6, 3, 2, 1]. The leftmost entry is 6, so gcd(12, 18) = 6.
3. A shortcutWe can stop at the first common entry, because it is already the greatest.

The first number that divides both m and n is the gcd, so we can report it and stop.

1. Algorithm
   1. Let k be the smaller of m and n.
   2. If k divides both m and n, report k as the gcd and stop.
   3. Otherwise reduce k by 1 and go back to Step 2.
2. Example: m = 12, n = 18Check 12, 11, 10, 9, 8, 7: none divides both numbers. Then 6 divides both, so we stop: gcd(12, 18) = 6.

gcd(375, 825) = 75.

1. Put the larger number first

   Step	Division	Quotient	Remainder
   1	825 = 375 × 2 + 75	2	75
   2	375 = 75 × 5 + 0	5	0

2. AnswerThe last non-zero divisor is 75, so gcd(375, 825) = 75.

gcd(51000, 81000) = 3000.

1. Divisions

   Step	Division	Quotient	Remainder
   1	81000 = 51000 × 1 + 30000	1	30000
   2	51000 = 30000 × 1 + 21000	1	21000
   3	30000 = 21000 × 1 + 9000	1	9000
   4	21000 = 9000 × 2 + 3000	2	3000
   5	9000 = 3000 × 3 + 0	3	0

2. AnswerThe last non-zero divisor is 3000, so gcd(51000, 81000) = 3000.

gcd(1789287, 237656) = 1 (the numbers are co-prime).

1. Divisions (13 steps)

   Step	Division	Quotient	Remainder
   1	1789287 = 237656 × 7 + 125695	7	125695
   2	237656 = 125695 × 1 + 111961	1	111961
   3	125695 = 111961 × 1 + 13734	1	13734
   4	111961 = 13734 × 8 + 2089	8	2089
   5	13734 = 2089 × 6 + 1200	6	1200
   6	2089 = 1200 × 1 + 889	1	889
   7	1200 = 889 × 1 + 311	1	311
   8	889 = 311 × 2 + 267	2	267
   9	311 = 267 × 1 + 44	1	44
   10	267 = 44 × 6 + 3	6	3
   11	44 = 3 × 14 + 2	14	2
   12	3 = 2 × 1 + 1	1	1
   13	2 = 1 × 2 + 0	2	0

2. AnswerThe last non-zero divisor is 1, so gcd(1789287, 237656) = 1.

gcd(2587392, 157656) = 24.

1. Divisions (7 steps)

   Step	Division	Quotient	Remainder
   1	2587392 = 157656 × 16 + 64896	16	64896
   2	157656 = 64896 × 2 + 27864	2	27864
   3	64896 = 27864 × 2 + 9168	2	9168
   4	27864 = 9168 × 3 + 360	3	360
   5	9168 = 360 × 25 + 168	25	168
   6	360 = 168 × 2 + 24	2	24
   7	168 = 24 × 7 + 0	7	0

2. AnswerThe last non-zero divisor is 24, so gcd(2587392, 157656) = 24.

The common divisors of m and n are exactly the common divisors of n and m mod n, so the gcd does not change.

1. Set upLet r = m mod n be the remainder when m is divided by n (n > 0). Then m = qn + r with 0 ≤ r < n, so r = m − qn.
2. If d divides m and n, then d divides n and rWrite m = ad and n = bd. Then r = m − qn = ad − qbd = (a − qb)d. So d divides r, and it already divides n.
3. If d divides n and r, then d divides m and nWrite n = bd and r = cd. Then m = qn + r = qbd + cd = (qb + c)d. So d divides m, and it already divides n.
4. ConclusionThe two pairs (m, n) and (n, r) have exactly the same common divisors, so they have the same greatest common divisor: gcd(m, n) = gcd(n, m mod n).

n is prime exactly when it has two positive divisors, 1 and n.

1. Algorithm prime(n)
   1. If n < 2, report “not prime” and stop.
   2. Use divisors(n) to find the list of the positive divisors of n.
   3. Count the entries in the list.
   4. If there are exactly two entries, report “prime”. Otherwise report “not prime”.
2. Examplesdivisors(7) = [1, 7]: exactly two, so 7 is prime. divisors(9) = [1, 3, 9]: three, so 9 is not prime. 1 is not prime, since it has only one divisor.

Find all the divisors of n and keep those that are prime.

1. Algorithm primedivisors(n)
   1. Use divisors(n) to find all the positive divisors of n.
   2. Start with an empty list called prime-divisors.
   3. Take each divisor d from left to right.
   4. Check whether d has exactly two positive divisors, 1 and d (use prime(d)).
   5. If d is prime, add it to prime-divisors.
   6. After all the divisors are checked, report prime-divisors.
2. Example: n = 180divisors(180) = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]. The primes among them are 2, 3 and 5, so primedivisors(180) = [2, 3, 5]. For n = 1 the answer is the empty list.

Each prime appears only once in this list. It does not say how many times a prime occurs in the factorisation; that is Question 22.

Represent 180 as the list of pairs [(2, 2), (3, 2), (5, 1)]. For the gcd, take each common prime with the smaller power.

1. The algorithm
   1. Let the given number be n. Set remaining = n.
   2. Use primedivisors(n) to list its prime divisors.
   3. Start with an empty list called factorisation.
   4. For each prime p in the list: set count = 0; while p divides remaining, divide remaining by p and increase count by 1; then add the pair (p, count) to factorisation.
   5. Report factorisation.
2. Example: n = 180Prime divisors = [2, 3, 5]. For p = 2: 180 ÷ 2 = 90, 90 ÷ 2 = 45; 45 is not divisible by 2, so record (2, 2). For p = 3: 45 ÷ 3 = 15, 15 ÷ 3 = 5, so record (3, 2). For p = 5: 5 ÷ 5 = 1, so record (5, 1).
3. (i) Representation[(2, 2), (3, 2), (5, 1)]. A pair (p, k) means that the prime p occurs k times: (2, 2) is 2², (3, 2) is 3², (5, 1) is 5¹. Their product is 4 × 9 × 5 = 180.
4. (ii) Comparing two factorisationsFind the primes that are in both lists. For each common prime, choose the smaller of its two powers. Multiply these powers: the product is the gcd. If there is no common prime, the gcd is 1.
5. Example: gcd(180, 252)180 = 2² × 3² × 5 and 252 = 2² × 3² × 7. The common primes are 2 and 3, each with smaller power 2. So gcd = 2² × 3² = 4 × 9 = 36.
6. Why the smaller power12 = 2² × 3 and 18 = 2 × 3². A common divisor can have only one factor 2 and one factor 3, because those are the numbers of copies that both numbers have. So gcd(12, 18) = 2 × 3 = 6.