Confirming your payment

Skip to content

Opening your dashboard

Class 9 Maths Chapter 11: The World of Algorithms Solutions

15 textbook questions with step-by-step answers, free to read, for CBSE 2026-27.

AI Tutor

Get talked through Ch 11, not just shown the answer

Reading a finished solution is not the same as being able to do it. The AI tutor takes one question at a time and works it with you, in your own words, until you can.

  • Ask it out loud, in your own words
  • It gives you the next step, not the answer
  • Stuck on part (ii)? Start there
Ch 11 solutions

15 questions with solutions

2–5 marks · Mixed difficulty

The first 12 solutions are on this page. This chapter is a long one, so the rest open on their own page to keep this one quick to load.

  1. 1

    Question 1

    Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?

    Medium
    3 marks
    Solve with AI
    Written solution

    Take the two 4-digit numbers 4738 and 2596.

    Step 1: Write the numbers one below the other with the digits aligned from right to left.

    Steps 2 to 4: Add the columns from right to left, one at a time, using the carry.

    The working, column by column:

    ColumnDigitsCarry inSumWriteCarry out
    units8 + 601441
    tens3 + 911331
    hundreds7 + 511331
    thousands4 + 21770

    Step 2 (units): 8+6=148 + 6 = 14, which is more than 10, so write 4 and set carry to 1.

    Step 3 (tens): 3+9+1=133 + 9 + 1 = 13, more than 10, so write 3 and set carry to 1.

    Step 4 repeats Step 3 (hundreds): 7+5+1=137 + 5 + 1 = 13, write 3, carry 1.

    Step 4 repeats Step 3 (thousands): 4+2+1=74 + 2 + 1 = 7, less than 10, write 7, carry 0. There are no more digits on the left.

    Step 5: The carry is 0, so nothing more is written.

    4738+  25967334\begin{array}{r} 4738 \\ +\;2596 \\ \hline 7334 \end{array}

    So 4738+2596=73344738 + 2596 = 7334, which is correct.

    But the steps do not always work when followed literally. Step 2 and Step 3 only say what to do when the sum is less than 10 or more than 10. They say nothing about a sum of exactly 10. Try 3347 + 2729:

    Units: 7+9=167 + 9 = 16, write 6, carry 1. Tens: 4+2+1=74 + 2 + 1 = 7, write 7, carry 0. Hundreds: 3+7+0=103 + 7 + 0 = 10. The sum is neither less than 10 nor more than 10, so the steps tell us neither what to write nor what carry to set. Following them precisely, we are stuck.

    If we read "more than 10" as "10 or more" (as the text before the algorithm says: carry when the total is equal to or more than 10), we write 0, carry 1, and then thousands: 3+2+1=63 + 2 + 1 = 6, giving 3347+2729=60763347 + 2729 = 6076, which is correct.

    Conclusion: For numbers where no column adds up to exactly 10, the steps give the correct result. To work for all numbers, the second case in Steps 2 and 3 should read "If the sum is 10 or more".

  2. 2

    Question 2

    What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?

    Medium
    3 marks
    Solve with AI
    Written solution

    Take 48765 + 734. Aligned from right to left, the 3-digit number has no digits in the thousands and ten thousands columns.

    ColumnDigitsCarry inSumWriteCarry out
    units5 + 40990
    tens6 + 30990
    hundreds7 + 701441
    thousands8 + (no digit)1990
    ten thousands4 + (no digit)0440

    Units: 5+4=95 + 4 = 9, write 9, carry 0. Tens: 6+3=96 + 3 = 9, write 9, carry 0. Hundreds: 7+7=147 + 7 = 14, write 4, carry 1.

    Thousands: Step 3 says "add the two digits and the current value of carry", but there is only one digit, 8. We must treat the missing digit as 0: 8+0+1=98 + 0 + 1 = 9, write 9, carry 0.

    Ten thousands: again only one digit, 4+0+0=44 + 0 + 0 = 4, write 4.

    48765+  73449499\begin{array}{r} 48765 \\ +\;734 \\ \hline 49499 \end{array}

    So 48765+734=4949948765 + 734 = 49499, which is correct.

    Do the steps handle this correctly? Only if we make an assumption the steps do not state. Step 3 speaks of "the two digits", and Step 4 says to repeat "until there are no more digits on the left", which does not make clear whether it means no more digits in either number or in both. If we stopped when the shorter number ran out, we would get only 499, which is wrong; and we would also have no rule for a carry going into a column that has just one digit.

    The steps work correctly if we add the rule: if one number has no digit in a column, take that digit to be 0 (equivalently, write 734 as 00734), and repeat Step 3 until both numbers have no more digits on the left.

  3. 3

    Question 3

    Why is it important to align the columns from right to left?

    Easy
    2 marks
    Solve with AI
    Written solution

    The algorithm adds digits that have the same place value: units with units, tens with tens, hundreds with hundreds, and so on. In the Indian place-value system the rightmost digit of every number is its units digit, so aligning from the right puts digits of equal place value in the same column.

    Numbers with different numbers of digits do not start with the same place value. If we align from the left, we add digits of different place values. For example, aligning 473 and 2695 from the left puts the 4 hundreds of 473 under the 2 thousands of 2695:

    47302695\begin{array}{l} 473\phantom{0} \\ 2695 \end{array}

    This actually adds 4730+2695=74254730 + 2695 = 7425, but the correct sum is 473+2695=3168473 + 2695 = 3168.

    Aligning from the right also makes sense of the carry: a carry from one column is a group of ten, and it must go into the column that is worth ten times as much, which is the next column to the left. So the columns must be aligned from right to left, and added from right to left.

  4. 4

    Question 4

    In Step 3, why cannot the value of carry be more than 1?

    Easy
    2 marks
    Solve with AI
    Written solution

    Each digit is at most 9.

    In Step 2 (the units column) there is no carry yet, so the largest possible sum is 9+9=189 + 9 = 18. This is less than 20, so the carry set in Step 2 is 0 or 1.

    In Step 3 we add two digits and a carry of at most 1, so the largest possible sum is

    9+9+1=199 + 9 + 1 = 19

    which is also less than 20. So the sum has a units digit and at most one ten, and the new carry is again 0 or 1.

    Since every column starts with a carry of at most 1 and produces a carry of at most 1, the carry can never be more than 1 at any column. (For example, 999+999=1998999 + 999 = 1998: every column gives 9+9+1=199 + 9 + 1 = 19 or 9+9=189 + 9 = 18, and every carry is 1.)

  5. 5

    Question 5

    What happens if we do not include the fifth step in the algorithm above? Give examples where the algorithm will work correctly and where it will fail to work.

    Medium
    3 marks
    Solve with AI
    Written solution

    Step 5 writes the final carry. Without it, a carry of 1 coming out of the leftmost column would simply be lost, and the answer would be short by one digit.

    The algorithm still works whenever the leftmost column adds up to less than 10, so the final carry is 0. For example, 473+215473 + 215: units 3+5=83 + 5 = 8, tens 7+1=87 + 1 = 8, hundreds 4+2=64 + 2 = 6, final carry 0, giving 688. This is correct, and Step 5 was not needed.

    The algorithm fails whenever the leftmost column produces a carry. For example, 473+695473 + 695: units 3+5=83 + 5 = 8, carry 0; tens 7+9=167 + 9 = 16, write 6, carry 1; hundreds 4+6+1=114 + 6 + 1 = 11, write 1, carry 1. Without Step 5 the bottom row reads 168, but the correct sum is 1168. Similarly, 9+39 + 3 would give 2 instead of 12, and 5000+60005000 + 6000 would give 1000 instead of 11000.

    So without Step 5 the algorithm is correct only when the sum has the same number of digits as the longer number.

  6. 6

    Question 6

    Suppose List 1 and List 2 are two lists of numbers in increasing order.

    (i) Write an algorithm to find elements in List 1 that are not present in List 2.

    (ii) Write an algorithm to find elements in List 2 that are not present in List 1.

    Medium
    4 marks
    Solve with AI
    Written solution

    (i) A simple algorithm, in the style of the gcd algorithm:

    1. Start with an empty list only-in-1.

    2. For each number xx in List 1: if xx does not appear in List 2, add xx to only-in-1.

    3. Report only-in-1.

    Because both lists are in increasing order, we can do better and go through each list only once, keeping a position in each list:

    1. Start with an empty list only-in-1. Let xx be the first element of List 1 and yy the first element of List 2.

    2. If List 2 is finished, add xx and all the remaining elements of List 1 to only-in-1, and go to Step 6.

    3. If x<yx < y: xx cannot appear later in List 2 (the later elements are even larger), so add xx to only-in-1 and move xx to the next element of List 1.

    4. If x=yx = y: xx is present in List 2, so move xx to the next element of List 1 and yy to the next element of List 2.

    5. If x>yx > y: move yy to the next element of List 2.

      After doing whichever one of Steps 3, 4 and 5 applies, repeat from Step 2 until List 1 is finished.

    6. Report only-in-1.

    Example. List 1 =[1,3,5,15,25,75,125,375]= [1, 3, 5, 15, 25, 75, 125, 375] (the divisors of 375) and List 2 =[1,3,5,11,15,25,33,55,75,165,275,825]= [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825] (the divisors of 825).

    • 1=11 = 1: 1 is in both lists; move on in both lists.
    • 3=33 = 3: 3 is in both lists; move on in both lists.
    • 5=55 = 5: 5 is in both lists; move on in both lists.
    • 15>1115 > 11: move on in List 2.
    • 15=1515 = 15: 15 is in both lists; move on in both lists.
    • 25=2525 = 25: 25 is in both lists; move on in both lists.
    • 75>3375 > 33: move on in List 2.
    • 75>5575 > 55: move on in List 2.
    • 75=7575 = 75: 75 is in both lists; move on in both lists.
    • 125<165125 < 165: 125 cannot be in List 2, so add 125 to the result.
    • 375>165375 > 165: move on in List 2.
    • 375>275375 > 275: move on in List 2.
    • 375<825375 < 825: 375 cannot be in List 2, so add 375 to the result.

    Result: elements of List 1 not in List 2 =[125,375]= [125, 375].

    (ii) This is the same algorithm with the roles of the two lists exchanged:

    1. Start with an empty list only-in-2. Let yy be the first element of List 2 and xx the first element of List 1.

    2. If List 1 is finished, add yy and all the remaining elements of List 2 to only-in-2, and go to Step 6.

    3. If y<xy < x: add yy to only-in-2 and move yy to the next element of List 2.

    4. If y=xy = x: move both yy and xx to the next elements of their lists.

    5. If y>xy > x: move xx to the next element of List 1.

      After doing whichever one of Steps 3, 4 and 5 applies, repeat from Step 2 until List 2 is finished.

    6. Report only-in-2.

    With the same two lists (now scanning List 2 against List 1):

    • 1=11 = 1: 1 is in both lists; move on in both lists.
    • 3=33 = 3: 3 is in both lists; move on in both lists.
    • 5=55 = 5: 5 is in both lists; move on in both lists.
    • 11<1511 < 15: 11 cannot be in List 1, so add 11 to the result.
    • 15=1515 = 15: 15 is in both lists; move on in both lists.
    • 25=2525 = 25: 25 is in both lists; move on in both lists.
    • 33<7533 < 75: 33 cannot be in List 1, so add 33 to the result.
    • 55<7555 < 75: 55 cannot be in List 1, so add 55 to the result.
    • 75=7575 = 75: 75 is in both lists; move on in both lists.
    • 165>125165 > 125: move on in List 1.
    • 165<375165 < 375: 165 cannot be in List 1, so add 165 to the result.
    • 275<375275 < 375: 275 cannot be in List 1, so add 275 to the result.
    • 825>375825 > 375: move on in List 1.
    • List 1 is finished, so 825 is added to the result.

    Result: elements of List 2 not in List 1 =[11,33,55,165,275,825]= [11, 33, 55, 165, 275, 825].

    Each step moves forward in at least one list, so the scan takes at most (length of List 1 + length of List 2) comparisons, instead of searching the whole of List 2 for every element of List 1.

  7. 7

    Question 7

    Describe an algorithm to compute the least common multiple (lcm) of two numbers.

    Medium
    3 marks
    Solve with AI
    Written solution

    The lcm of mm and nn is the smallest number that is a multiple of both. The multiples of mm are m,2m,3m,…m, 2m, 3m, \ldots, so we check them in increasing order and stop at the first one that nn divides.

    Algorithm to find lcm(m, n)

    1. Set kk to 1.

    2. If nn divides k×mk \times m, report k×mk \times m as lcm(m, n) and stop.

    3. Otherwise, increase kk by 1 and repeat Step 2.

    The algorithm always stops: when k=nk = n, the number k×m=n×mk \times m = n \times m is a multiple of both, so we never go beyond k=nk = n. Since we check the multiples of mm in increasing order, the first common multiple we meet is the least one. (It is quicker to take mm as the larger of the two numbers, so fewer multiples are checked.)

    Example 1: lcm(18, 12), with m=18m = 18, n=12n = 12.

    • k=1k = 1: 18; 12 does not divide 18.

    • k=2k = 2: 36; 12 divides 36. Report lcm(18, 12) = 36.

    Example 2: lcm(825, 375), with m=825m = 825, n=375n = 375. The multiples of 825 are 825, 1650, 2475, 3300, 4125. 375 does not divide the first four, but 4125=11×3754125 = 11 \times 375. So lcm(825, 375) = 4125.

    Another way, using a gcd algorithm from this chapter: compute d=gcd⁡(m,n)d = \gcd(m, n) and report m×nd\dfrac{m \times n}{d}. For example, gcd⁡(375,825)=75\gcd(375, 825) = 75, so

    lcm(375,825)=375×82575=5×825=4125\text{lcm}(375, 825) = \frac{375 \times 825}{75} = 5 \times 825 = 4125

    which agrees with Example 2.

  8. 8

    Question 8

    (Challenge) Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).

    (i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and nn to find all the divisors of nn?

    (ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?

    Medium
    4 marks
    Solve with AI
    Written solution

    (i) If jj divides nn, then so does n÷jn \div j, and j×(n÷j)=nj \times (n \div j) = n. In each pair, the smaller number jj satisfies j×j≤nj \times j \le n (if both numbers of a pair were larger than this, their product would be more than nn).

    So we only need to examine the numbers j=1,2,3,…j = 1, 2, 3, \ldots while j×j≤nj \times j \le n. Each time jj divides nn, we write down the pair (j,n÷j)(j, n \div j). The number of values to examine is the largest whole number whose square is at most nn, that is, about n\sqrt{n}, instead of nn.

    For 18: 4×4=16≤184 \times 4 = 16 \le 18 but 5×5=25>185 \times 5 = 25 > 18, so we examine only 1, 2, 3, 4 (4 numbers instead of 18) and get the pairs (1, 18), (2, 9), (3, 6). For 825 we examine 1 to 28 (since 28×28=78428 \times 28 = 784 and 29×29=84129 \times 29 = 841), 28 numbers instead of 825.

    (When nn is a perfect square, one pair has two equal numbers, for example (6, 6) for 36, and we write that divisor only once.)

    (ii) Not without a change. Our gcd algorithm reports the rightmost element of the list of common divisors, which is the gcd only because the lists of divisors are in increasing order. A list written in pairs is not in increasing order: for 18 it is [1, 18, 2, 9, 3, 6].

    Try gcd(375, 825). Written in pairs,

    divisors(375) =[1,375,3,125,5,75,15,25]= [1, 375, 3, 125, 5, 75, 15, 25]

    divisors(825) =[1,825,3,275,5,165,11,75,15,55,25,33]= [1, 825, 3, 275, 5, 165, 11, 75, 15, 55, 25, 33]

    Checking each divisor of 375 in turn against the second list gives the common divisors [1,3,5,75,15,25][1, 3, 5, 75, 15, 25]. The rightmost element is 25, but gcd⁡(375,825)=75\gcd(375, 825) = 75. So the algorithm, as described, gives a wrong answer.

    To make it work, change the last step to "report the largest element of common-divisors" (scan the list keeping the largest so far), or first arrange the divisors in increasing order (write the smaller numbers of the pairs from left to right, then the larger numbers from right to left). With either change the answer is 75, and the algorithm is still correct.

  9. 9

    Question 9

    How would our original algorithm change if we computed the divisors of nn by examining the numbers from 1 to nn in reverse order, from nn down to 1?

    Medium
    3 marks
    Solve with AI
    Written solution

    Examining j=n,n−1,…,1j = n, n - 1, \ldots, 1 still finds every divisor, but the list of divisors is now in decreasing order. For 825 it is [825,275,165,75,55,33,25,15,11,5,3,1][825, 275, 165, 75, 55, 33, 25, 15, 11, 5, 3, 1].

    If only divisors-of-n is reversed (divisors-of-m still in increasing order): Step 4 only asks whether each xx in divisors-of-m appears in divisors-of-n, which does not depend on order. The list common-divisors is built in the order of divisors-of-m, so it is still increasing. For gcd(375, 825) it is [1,3,5,15,25,75][1, 3, 5, 15, 25, 75], and Step 5 (report the rightmost element) still gives 75. Nothing needs to change.

    If we compute every list of divisors in reverse order (so divisors-of-m is reversed too), common-divisors comes out in decreasing order: for gcd(375, 825) it is [75,25,15,5,3,1][75, 25, 15, 5, 3, 1]. Now the gcd is the leftmost element, so Step 5 must change to "Report the leftmost (first) element of the list common-divisors as gcd(m, n)". Reporting the rightmost element would give 1, which is wrong.

    This version has a bonus: the first common divisor we find is already the gcd, so in Step 4 we can stop as soon as we find one xx that appears in divisors-of-n; there is no need to build the whole list.

  10. 10

    Question 10

    What about the last algorithm described above? What happens when we look at common divisors starting from min⁡(m,n)\min(m, n) and work backwards to 1?

    Medium
    3 marks
    Solve with AI
    Written solution

    In the last algorithm, most-recent-common-divisor is updated every time we find a common divisor. Scanning upwards, each new common divisor is larger, so the last one found is the gcd.

    If we scan backwards, from min⁡(m,n)\min(m, n) down to 1, the common divisors appear in decreasing order. The first common divisor we meet is the greatest one, so it is the gcd. If we kept updating most-recent-common-divisor, it would be overwritten by smaller and smaller common divisors and end up as 1, which is wrong. So the algorithm changes to:

    1. For each kk from min⁡(m,n)\min(m, n) down to 1: if kk divides both mm and nn, report kk as gcd(m, n) and stop.

    The scan always stops, at the latest when k=1k = 1, because 1 divides every number. We do not even need the starting value 1 for most-recent-common-divisor.

    Example 1: m=6m = 6, n=12n = 12. min⁡(6,12)=6\min(6, 12) = 6, and k=6k = 6 divides both 6 and 12, so gcd⁡(6,12)=6\gcd(6, 12) = 6 after just 1 check (the upward scan needed 5 checks, k=2k = 2 to 6).

    Example 2: gcd(375, 825). We check k=375,374,…k = 375, 374, \ldots and the first kk dividing both is 75. That is 375−75+1=301375 - 75 + 1 = 301 checks, against 375−2+1=374375 - 2 + 1 = 374 checks for the upward scan from 2 to 375.

    So working backwards gives the same answer and usually saves work, because we stop early. But in the worst case, when the gcd is 1, we still examine every number from min⁡(m,n)\min(m, n) down to 1; for example gcd(100, 99) takes 99 checks. The work still grows with the value of the numbers, not with the number of digits.

  11. 11

    Question 11

    Compute the following using the improved version of Euclid's algorithm.

    (i) gcd⁡(375,825)\gcd(375, 825)

    (ii) gcd⁡(51000,81000)\gcd(51000, 81000)

    (iii) gcd⁡(1789287,237656)\gcd(1789287, 237656)

    (iv) gcd⁡(2587392,157656)\gcd(2587392, 157656)

    Medium
    5 marks
    Solve with AI
    Written solution

    The improved (division) version of Euclid's algorithm for gcd⁡(m,n)\gcd(m, n):

    1. If m<nm < n, reverse the numbers and compute gcd⁡(n,m)\gcd(n, m).

    2. If n=0n = 0, report the answer as mm.

    3. Otherwise, reduce the problem to computing gcd⁡(n,m mod n)\gcd(n, m \bmod n), where m mod nm \bmod n is the remainder when mm is divided by nn.

    (i) gcd⁡(375,825)\gcd(375, 825)

    Since 375<825375 < 825, Step 1 reverses the numbers: compute gcd⁡(825,375)\gcd(825, 375).

    825=2×375+75825 = 2 \times 375 + 75, so 825 mod 375=75825 \bmod 375 = 75. Step 3 reduces the problem to gcd⁡(375,75)\gcd(375, 75).

    375=5×75+0375 = 5 \times 75 + 0, so 375 mod 75=0375 \bmod 75 = 0. Step 3 reduces the problem to gcd⁡(75,0)\gcd(75, 0).

    Since n=0n = 0, Step 2 gives the answer gcd⁡(375,825)=75\gcd(375, 825) = 75.

    Number of reductions: 2. So gcd⁡(375,825)=75\gcd(375, 825) = 75.

    (ii) gcd⁡(51000,81000)\gcd(51000, 81000)

    Since 51000<8100051000 < 81000, Step 1 reverses the numbers: compute gcd⁡(81000,51000)\gcd(81000, 51000).

    81000=1×51000+3000081000 = 1 \times 51000 + 30000, so 81000 mod 51000=3000081000 \bmod 51000 = 30000. Step 3 reduces the problem to gcd⁡(51000,30000)\gcd(51000, 30000).

    51000=1×30000+2100051000 = 1 \times 30000 + 21000, so 51000 mod 30000=2100051000 \bmod 30000 = 21000. Step 3 reduces the problem to gcd⁡(30000,21000)\gcd(30000, 21000).

    30000=1×21000+900030000 = 1 \times 21000 + 9000, so 30000 mod 21000=900030000 \bmod 21000 = 9000. Step 3 reduces the problem to gcd⁡(21000,9000)\gcd(21000, 9000).

    21000=2×9000+300021000 = 2 \times 9000 + 3000, so 21000 mod 9000=300021000 \bmod 9000 = 3000. Step 3 reduces the problem to gcd⁡(9000,3000)\gcd(9000, 3000).

    9000=3×3000+09000 = 3 \times 3000 + 0, so 9000 mod 3000=09000 \bmod 3000 = 0. Step 3 reduces the problem to gcd⁡(3000,0)\gcd(3000, 0).

    Since n=0n = 0, Step 2 gives the answer gcd⁡(51000,81000)=3000\gcd(51000, 81000) = 3000.

    Number of reductions: 5. So gcd⁡(51000,81000)=3000\gcd(51000, 81000) = 3000.

    (iii) gcd⁡(1789287,237656)\gcd(1789287, 237656)

    1789287=7×237656+1256951789287 = 7 \times 237656 + 125695, so 1789287 mod 237656=1256951789287 \bmod 237656 = 125695. Step 3 reduces the problem to gcd⁡(237656,125695)\gcd(237656, 125695).

    237656=1×125695+111961237656 = 1 \times 125695 + 111961, so 237656 mod 125695=111961237656 \bmod 125695 = 111961. Step 3 reduces the problem to gcd⁡(125695,111961)\gcd(125695, 111961).

    125695=1×111961+13734125695 = 1 \times 111961 + 13734, so 125695 mod 111961=13734125695 \bmod 111961 = 13734. Step 3 reduces the problem to gcd⁡(111961,13734)\gcd(111961, 13734).

    111961=8×13734+2089111961 = 8 \times 13734 + 2089, so 111961 mod 13734=2089111961 \bmod 13734 = 2089. Step 3 reduces the problem to gcd⁡(13734,2089)\gcd(13734, 2089).

    13734=6×2089+120013734 = 6 \times 2089 + 1200, so 13734 mod 2089=120013734 \bmod 2089 = 1200. Step 3 reduces the problem to gcd⁡(2089,1200)\gcd(2089, 1200).

    2089=1×1200+8892089 = 1 \times 1200 + 889, so 2089 mod 1200=8892089 \bmod 1200 = 889. Step 3 reduces the problem to gcd⁡(1200,889)\gcd(1200, 889).

    1200=1×889+3111200 = 1 \times 889 + 311, so 1200 mod 889=3111200 \bmod 889 = 311. Step 3 reduces the problem to gcd⁡(889,311)\gcd(889, 311).

    889=2×311+267889 = 2 \times 311 + 267, so 889 mod 311=267889 \bmod 311 = 267. Step 3 reduces the problem to gcd⁡(311,267)\gcd(311, 267).

    311=1×267+44311 = 1 \times 267 + 44, so 311 mod 267=44311 \bmod 267 = 44. Step 3 reduces the problem to gcd⁡(267,44)\gcd(267, 44).

    267=6×44+3267 = 6 \times 44 + 3, so 267 mod 44=3267 \bmod 44 = 3. Step 3 reduces the problem to gcd⁡(44,3)\gcd(44, 3).

    44=14×3+244 = 14 \times 3 + 2, so 44 mod 3=244 \bmod 3 = 2. Step 3 reduces the problem to gcd⁡(3,2)\gcd(3, 2).

    3=1×2+13 = 1 \times 2 + 1, so 3 mod 2=13 \bmod 2 = 1. Step 3 reduces the problem to gcd⁡(2,1)\gcd(2, 1).

    2=2×1+02 = 2 \times 1 + 0, so 2 mod 1=02 \bmod 1 = 0. Step 3 reduces the problem to gcd⁡(1,0)\gcd(1, 0).

    Since n=0n = 0, Step 2 gives the answer gcd⁡(1789287,237656)=1\gcd(1789287, 237656) = 1.

    Number of reductions: 13. So gcd⁡(1789287,237656)=1\gcd(1789287, 237656) = 1.

    (iv) gcd⁡(2587392,157656)\gcd(2587392, 157656)

    2587392=16×157656+648962587392 = 16 \times 157656 + 64896, so 2587392 mod 157656=648962587392 \bmod 157656 = 64896. Step 3 reduces the problem to gcd⁡(157656,64896)\gcd(157656, 64896).

    157656=2×64896+27864157656 = 2 \times 64896 + 27864, so 157656 mod 64896=27864157656 \bmod 64896 = 27864. Step 3 reduces the problem to gcd⁡(64896,27864)\gcd(64896, 27864).

    64896=2×27864+916864896 = 2 \times 27864 + 9168, so 64896 mod 27864=916864896 \bmod 27864 = 9168. Step 3 reduces the problem to gcd⁡(27864,9168)\gcd(27864, 9168).

    27864=3×9168+36027864 = 3 \times 9168 + 360, so 27864 mod 9168=36027864 \bmod 9168 = 360. Step 3 reduces the problem to gcd⁡(9168,360)\gcd(9168, 360).

    9168=25×360+1689168 = 25 \times 360 + 168, so 9168 mod 360=1689168 \bmod 360 = 168. Step 3 reduces the problem to gcd⁡(360,168)\gcd(360, 168).

    360=2×168+24360 = 2 \times 168 + 24, so 360 mod 168=24360 \bmod 168 = 24. Step 3 reduces the problem to gcd⁡(168,24)\gcd(168, 24).

    168=7×24+0168 = 7 \times 24 + 0, so 168 mod 24=0168 \bmod 24 = 0. Step 3 reduces the problem to gcd⁡(24,0)\gcd(24, 0).

    Since n=0n = 0, Step 2 gives the answer gcd⁡(2587392,157656)=24\gcd(2587392, 157656) = 24.

    Number of reductions: 7. So gcd⁡(2587392,157656)=24\gcd(2587392, 157656) = 24.

    Final answers: (i) 75, (ii) 3000, (iii) 1, (iv) 24. Note that (iii), with 7-digit numbers, needed only 13 reductions, while the subtraction version needed 7 reductions for the much smaller pair 375 and 825 in (i).

  12. 12

    Question 12

    Assume that m≥nm \ge n. Verify that dd divides mm and nn if and only if dd divides both nn and m mod nm \bmod n.

    Medium
    3 marks
    Solve with AI
    Written solution

    Divide mm by nn: let qq be the quotient and r=m mod nr = m \bmod n the remainder, so

    m=qn+r,that is,r=m−qnm = q n + r, \quad \text{that is,} \quad r = m - q n

    (This is the same as subtracting nn from mm repeatedly, qq times.)

    If dd divides mm and nn: write m=adm = a d and n=bdn = b d for natural numbers aa, bb. Then

    r=m−qn=ad−qbd=(a−qb)dr = m - q n = a d - q b d = (a - q b) d

    so dd divides r=m mod nr = m \bmod n (when r=0r = 0 this still holds, since 0=0×d0 = 0 \times d). And dd divides nn already. So dd divides both nn and m mod nm \bmod n.

    If dd divides nn and m mod nm \bmod n: write n=xdn = x d and r=ydr = y d for whole numbers xx, yy. Then

    m=qn+r=qxd+yd=(qx+y)dm = q n + r = q x d + y d = (q x + y) d

    so dd divides mm. And dd divides nn already. So dd divides both mm and nn.

    In terms of tiles: if blocks of size dd tile mm and nn, then removing qq copies of nn from mm leaves rr, which is also tiled; and putting qq copies of nn back onto rr gives mm, which is tiled.

    Check with numbers: m=60m = 60, n=16n = 16, 60=3×16+1260 = 3 \times 16 + 12, so 60 mod 16=1260 \bmod 16 = 12. The common divisors of 60 and 16 are 1, 2, 4, and the common divisors of 16 and 12 are also 1, 2, 4. The two sets of common divisors are the same, so gcd⁡(60,16)=gcd⁡(16,12)=4\gcd(60, 16) = \gcd(16, 12) = 4. This is exactly why the improved Euclid algorithm may replace gcd⁡(m,n)\gcd(m, n) by gcd⁡(n,m mod n)\gcd(n, m \bmod n).

  13. 13

    Question 13

    Write an algorithm prime(n)\text{prime}(n) to check if nn is prime.

    (Hint: A prime number pp has exactly two distinct factors, 1 and pp. Can you make use of divisors(n)\text{divisors}(n) to write out prime(n)\text{prime}(n)?)

    Medium
    3 marks
  14. 14

    Question 14

    (Challenge) Write an algorithm primedivisors(n)\text{primedivisors}(n) to compute the list of divisors of nn that are prime numbers.

    (Hint: Compute divisors(n)\text{divisors}(n) and then filter out the primes in this list.)

    Medium
    3 marks
  15. 15

    Question 15

    (Challenge) We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number.

    (i) The prime factorisation of 180 is 22×32×512^2 \times 3^2 \times 5^1. How would you represent this?

    (ii) How would you compare the prime factorisations of two numbers?

    Medium
    4 marks
Inside Ch 11

What Class 9 Maths Ch 11 covers

The sections of the chapter, in the order the book takes them. Every question above comes from one of these.

  1. 01Adding Numbers
  2. 02Greatest Common Divisor
  3. 03Data Structures
Common questions

Class 9 Maths Ch 11 questions students ask

How many questions are there in Class 9 Maths Ch 11?

15 questions. Every one is solved step by step on this page.

Are these Class 9 Maths solutions free?

Yes. Every question and its full working is free to read, with no account needed.

Can I download the Class 9 Maths Ch 11 solutions as a PDF?

There is no PDF to download. Every solution is on this page instead, which means it is searchable, always the current syllabus, and readable on a phone. Use your browser's print option if you want it on paper.