Class 9 Maths Chapter 11: The World of Algorithms — Notes, Examples & Practice

An algorithm is a finite sequence of clear, unambiguous steps that takes an input, and after a finite number of steps produces an output — the same output every time for the same input.

Column addition is an algorithm: line up the digits by place value, add the units column, write the units digit of the sum and carry the tens digit, then repeat for each column to the left. It works for any two numbers, however long, which is the point of an algorithm.

Good algorithms have three properties: every step is precise, the process always stops, and it gives the correct answer. Among correct algorithms we prefer the one that takes fewer steps — it is more efficient.

A divisor of $n$ divides it with no remainder. The greatest common divisor $\gcd(a, b)$ (also called HCF) is the largest number that divides both. The least common multiple $\text{lcm}(a, b)$ is the smallest positive number both divide.

The simplest GCD algorithm lists all divisors of each number and picks the largest common one. It works, but for large numbers listing divisors is slow — this motivates better methods.

A key link: for positive integers, $\gcd(a, b) \times \text{lcm}(a, b) = a \times b$. So once you know the GCD, the LCM costs one multiplication and one division.

Euclid (around 300 BCE) noticed: **any number that divides both $a$ and $b$ also divides $a - b$**, and vice versa. So $\gcd(a, b) = \gcd(a - b, b)$ when $a > b$.

Algorithm: while the two numbers are different, replace the larger by (larger − smaller). When they become equal, that number is the GCD.

It always stops, because the numbers keep getting smaller but stay positive. However, if one number is much larger than the other, it takes many subtractions.

Repeated subtraction of $b$ from $a$ is just division: subtracting $b$ as many times as possible leaves the remainder. So $\gcd(a, b) = \gcd(b, r)$ where $a = bq + r$, $0 \le r < b$.

Algorithm: divide the larger by the smaller, then replace the pair by (smaller, remainder). Repeat until the remainder is 0. The last non-zero remainder (the last divisor) is the GCD. Āryabhaṭa (5th century CE) used this method, called kuṭṭaka, and extended it to solve equations like $ax - by = c$ in whole numbers.

This is far faster than subtraction: gcd(1000, 3) by subtraction needs over 300 steps; by division it needs 2.

Algorithms often store intermediate results in a list (a simple data structure) — for example the divisors found so far, or the primes already known.

**Is $n$ prime?** Try dividing by 2, 3, 4, … but only up to $\sqrt{n}$: if $n = a \times b$ with both factors bigger than $\sqrt{n}$, their product would exceed $n$. This one observation makes the test much faster. You can also skip even numbers after 2.

Prime factorisation: divide by the smallest prime that works, write it in the list, and repeat with the quotient until 1 is left. The list is the factorisation, and it is unique (apart from order).