CBSE Class 9 · NCERT Ganita Manjari, Part II · Chapter 11

Chapter 11: The World of Algorithms

Step-by-step procedures: column addition, divisor lists, gcd by scanning, and Euclid's and Āryabhaṭa's fast methods. This chapter is broken into 14 skills; each has an animated lesson and practice questions that never repeat.

What you learn in Chapter 11

  1. Skill 1

    Where the word algorithm came from

    Al-Khwārizmī wrote on Indian numerals around 820 CE; Euclid wrote down the subtraction gcd; Āryabhaṭa (499 CE) used division.

  2. Skill 2

    What an algorithm is

    Precise steps built from basic steps we can already do, with repeated steps, conditions, named values and a stopping rule.

  3. Skill 3

    Adding digit by digit with a carry

    Align from the right, add each column with the carry, carry 1 when a column reaches 10, and write the last carry.

  4. Skill 4

    Counting dots or adding columns

    Counting takes as many steps as the sum; columns take one step per digit. One more digit: 10 times the dots, one more column.

  5. Skill 5

    The divisors(n) algorithm

    Start with an empty list; for each j from 1 to n, add j if it divides n. divisors(18) = [1, 2, 3, 6, 9, 18].

  6. Skill 6

    Divisors come in pairs

    Every divisor j ≤ √n has a partner n ÷ j, so checking 1 to √n is enough. 18: (1, 18), (2, 9), (3, 6).

  7. Skill 7

    First gcd algorithm: common divisors from two lists

    Keep each divisor of m that is also in divisors(n); the lists are increasing, so the gcd is the rightmost common divisor.

  8. Skill 8

    Improving the gcd algorithm

    One scan to max(m, n), then only to min(m, n), then no list at all: keep the most-recent-common-divisor.

  9. Skill 9

    How many steps? Analysing an algorithm

    Scanning to min(m, n) grows 10 times per extra digit; good algorithms grow with the number of digits instead.

  10. Skill 10

    Euclid's subtraction algorithm

    gcd(m, n) = gcd(n, m − n), and gcd(m, 0) = m. Swap if m < n, subtract, repeat. gcd(375, 825) takes 7 reductions.

  11. Skill 11

    Āryabhaṭa's division algorithm

    Replace m − n by m mod n, the remainder: gcd(99, 2) takes 2 reductions instead of 51. Long division layout.

  12. Skill 12

    Algorithms for primes and prime factors

    n is prime when divisors(n) has exactly two entries; filter divisors(n) for the primes; 180 = 2² × 3² × 5¹.

  13. Skill 13

    An algorithm for the lcm

    Scan multiples of the larger number until one is a multiple of the smaller, or use gcd × lcm = m × n.

  14. Skill 14

    Algorithms on textbook problems

    gcd(51000, 81000), gcd(2587392, 157656), counting reductions, divisor lists and carries from the exercises.

Free lesson · What an algorithm is

Reading the divisors algorithm as an algorithm

An algorithm is a systematic, step-by-step procedure to solve a problem. Each step is written precisely and uses only basic steps we already know how to do, such as adding two single digits or checking whether one number divides another.

Steps can repeat (for each j from 1 to n …), can be conditional (… if j divides n, add j), use named values (j, list-of-divisors), and must stop. When we give an algorithm we also justify that it is correct, and we can count how many steps it takes.

1. list-of-divisors = [ ]2. for each j in 1, 2, …, n: if j divides n: add j
Start

1. Start with an empty list-of-divisors. 2. For each number j in 1, 2, 3, …, n: if j divides n, add j to list-of-divisors.

Remember: Algorithm = precise basic steps, repeated and conditional, with names, a stop, and a reason it works.

Sample questions with solutions

In the portal every question is generated fresh, so you never see the same one twice, and a wrong answer tells you which mistake you made.

Question 1 · The divisors(n) algorithm

How many values of j does divisors(63) check, as written in the book?

Show answer and solution

Answer: 63

  • The algorithm checks every j from 1 to 63.
  • 63 checks, whatever the number of divisors. Divisor pairs can cut this to about √63.
Question 2 · Improving the gcd algorithm

Running the most-recent-common-divisor scan for gcd(81, 63), what is its value just after k = 6 is checked?

Show answer and solution

Answer: 3

  • Common divisors up to 6: [1, 3].
  • The most recent one is 3.
Question 3 · Algorithms on textbook problems

divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375] and divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]. What is gcd(375, 825)?

Show answer and solution

Answer: 75

  • Common divisors: [1, 3, 5, 15, 25, 75]; 125 and 375 are not in the second list.
  • The rightmost, 75, is the gcd.

Common mistakes in this chapter

  • Missed a divisor

    Check every j from 1 to n, including 1 and n itself, or find the partner n ÷ j of each small divisor.

  • Stopped at the wrong place

    The algorithm stops at gcd(m, 0), and the answer is m, the non-zero number.

  • Misread how an algorithm works

    An algorithm is a precise list of basic steps: some repeat, some happen only when a condition holds, and it must stop.

  • Mixed up value and number of digits

    One more digit makes a number about 10 times bigger: scanning work grows 10 times, column work by one step.

  • Used a divisor of only one number

    A common divisor must divide both numbers: check it against both lists.

Where is this used?

  • Recipes, instructions and checklists

    A recipe is an algorithm: precise steps, some repeated ('stir every minute'), some conditional ('if it is too thick, add water'), and a clear point where you stop.

  • Adding a bill at the shop

    The shopkeeper adding ₹473 and ₹695 on paper runs the column algorithm: right to left, digit plus carry. Nobody counts 1168 coins one by one.

  • Cutting tiles and packing sweets

    The largest square tile that fits a 375 cm by 825 cm floor exactly, or the biggest equal boxes for 84 laddoos and 126 barfis, is a gcd: 75 cm and 42 per box.

  • When do two buses meet again?

    One bus every 12 minutes, another every 18: they leave together again after lcm(12, 18) = 36 minutes. Festivals, shift rotas and traffic lights work the same way.

Find your gap in Chapter 11

Log in with your phone number: lessons for all 14 skills, endless practice, a chapter test and a report that shows exactly what to fix.

Start with your phone number