EDURAClass 9 Notes
YouTube

Class 9 Maths · Chapter 11 · Part 2 (released 21 Sep 2026)

The World of Algorithms

Full chapter notes based on the NCERT 2026-27 textbook Ganita Manjari.

Chapter at a glance

An algorithm is a step-by-step procedure for solving a problem. This chapter writes algorithms precisely, justifies that they are correct, and compares how efficient they are, using column addition and the gcd (HCF) as examples. It ends with Euclid’s subtraction algorithm and Āryabhaṭa’s division algorithm.

11.1 Adding numbers digit by digit

Counting dots works for 5 + 7 but not for 473 + 695. Column addition is our first algorithm:

  1. Write the numbers one below the other, digits aligned from the right (place value).
  2. Add the rightmost digits. If the sum is less than 10, write it and set carry = 0; otherwise write the units digit and set carry = 1.
  3. Move one column left; add the two digits and the carry, using the same rule.
  4. Repeat Step 3 until no digits are left.
  5. If carry = 1, write 1 at the far left.
  • Basic step assumed: we can add single digits directly. Every algorithm is built from such basic steps.
  • Why it works: we group each number into units, tens, hundreds and add each group; every ten units formed is carried to the tens group.
  • Carry is never more than 1: the largest column sum is 9 + 9 + 1 = 19.
  • Efficiency: going from 3-digit to 4-digit numbers means 10× as many dots to count, but only one more column to add. The effort grows with the number of digits, not the size of the number. (Counting one dot per second, 3347 + 2729 takes over 1 hour 40 minutes; column addition takes about a minute.)

11.2 Greatest common divisor from the definition

Break the problem down: (1) list the divisors of each number, (2) find the largest number in both lists.

Algorithm: divisors(n)

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

Executing it for 18 gives [1, 2, 3, 6, 9, 18], already in increasing order.

First algorithm: gcd(m, n)

  1. divisors-of-m = divisors(m); divisors-of-n = divisors(n)
  2. Start with an empty list common-divisors.
  3. For each x in divisors-of-m: if x is also in divisors-of-n, add x to common-divisors.
  4. Report the rightmost (largest) element as gcd(m, n).

Example: divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375]; divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825]. Common divisors = [1, 3, 5, 15, 25, 75], so gcd(375, 825) = 75. For 54000 and 81000, the gcd is 27000.

Words to know: executing an algorithm means running through its steps. A list such as [1, 4, 9, 16] is an example of a data structure, a way of organising information so that an algorithm can be efficient. Giving names (j, list-of-divisors) to intermediate values keeps algorithms concise.

11.3 Improving the algorithm

  1. One combined scan: check each j from 1 to max(m, n) against both numbers: max(m, n) checks instead of m + n.
  2. Common divisors directly: add j only if it divides both, and stop at min(m, n), since a common divisor cannot exceed the smaller number.
  3. No lists at all: keep only most-recent-common-divisor. Start at 1, and for k = 2 to min(m, n), if k divides both, update it to k. At the end it is the gcd. (For 6 and 12: 1 → 2 → 3 → 6.)

These refinements are faster but compute the same thing, so they are still correct. They are still slow, though: the work grows with the value of min(m, n). Going from 3 to 5 digits means 100× more work.

11.3.3 Euclid’s subtraction algorithm

Key fact

If m ≥ n, then gcd(m, n) = gcd(n, m − n).

Why: if d divides m = ad and n = bd, then m − n = (a − b)d. Conversely, if d divides n = xd and m − n = yd, then m = (x + y)d. Both pairs have exactly the same common divisors. Pictorially, blocks of size d that tile m and n also tile m − n.

Euclid’s algorithm for gcd(m, n)

  1. If m < n, swap them and compute gcd(n, m).
  2. If n = 0, the answer is m.
  3. Otherwise reduce to gcd(n, m − n).

Trace for gcd(375, 825): (825, 375) → (375, 450) → (450, 375) → (375, 75) → (75, 300) → … → (75, 75) → (75, 0), so the answer is 75 after 7 reductions.

Weakness: gcd(99, 2) → (97, 2) → (95, 2) → … → (1, 0) needs about 50 steps. For gcd(2k + 1, 2) it needs about k steps, so the work still grows with the value of the number.

11.3.4 Āryabhaṭa’s division algorithm

Repeated subtraction of n from m leaves the remainder. So replace the subtraction step by one division:

Improved algorithm

  1. If m < n, swap.
  2. If n = 0, the answer is m.
  3. Otherwise reduce to gcd(n, m mod n), where m mod n is the remainder of m ÷ n (17 mod 5 = 2, 33 mod 7 = 5).
  • gcd(99, 2) → gcd(2, 1) → gcd(1, 0) = 1, just two reductions.
  • gcd(825, 375): 825 = 2 × 375 + 75, then 375 = 5 × 75 + 0, so the gcd is 75.
  • gcd(60, 16) → gcd(16, 12) → gcd(12, 4) → gcd(4, 0) = 4.

This is the “long division” method found in Āryabhaṭa’s Āryabhaṭīya (499 CE). The number of reductions is proportional to the number of digits (proof in later grades).

Where the word comes from: the Persian scholar Al-Khwārizmī (780–850 CE) of Baghdad’s House of Wisdom learnt Sanskrit and, around 820 CE, wrote on the Indian place-value system and arithmetic. Its Latin translation, Liber Algorismi de numero Indorum, spread these methods in Europe. Algorismus became “algorism” and then algorithm, which originally meant an Indian method of arithmetic.

Practice (End-of-chapter exercises)

  1. Use the improved Euclid algorithm: gcd(375, 825), gcd(51000, 81000), gcd(1789287, 237656), gcd(2587392, 157656). 75, 3000, 1, 24
  2. Write prime(n). Compute divisors(n); n is prime exactly when the list has two elements, [1, n].
  3. Write primedivisors(n). Compute divisors(n) and keep only those d with prime(d) true.
  4. Describe an algorithm for lcm(m, n). One way: check m, 2m, 3m, … and report the first that n divides. A faster way: lcm = m × n ÷ gcd(m, n).
  5. Divisors come in pairs, e.g. (1, 18), (2, 9), (3, 6). How far must you check to find all divisors of n? Only up to √n; each j found gives its partner n ÷ j.

Chapter summary

  • An algorithm is a systematic procedure built from basic steps we know how to execute.
  • Steps can repeat (for each j in 1, 2, …, n) and can be conditional (add j only if j divides n).
  • Every algorithm must be justified as correct, and can be analysed for how many steps it takes as the input grows.
  • gcd(m, n) = gcd(n, m − n) = gcd(n, m mod n). The division version is fast: its effort grows with the number of digits.

Source: NCERT, Ganita Manjari, Grade 9 (2026-27). NCERT chapter PDF. Spotted a mistake? Email edura.class9.yt@gmail.com. Last updated 11 October 2026.