1. Chapter at a Glance
A recipe, the steps to tie a shoelace, the method you learnt for adding big numbers — each is an algorithm: a precise, step-by-step procedure that always finishes and always gives the right answer. Computers run on algorithms, but algorithms are much older than computers. More than 2,300 years ago, Euclid described a brilliant method for finding the greatest common divisor of two numbers that is still used today. In this chapter we design algorithms, justify why they work, and compare how efficient they are.
- What an algorithm is: input, output, finite clear steps.
- The column addition algorithm and why "carrying" works.
- GCD (HCF) by listing divisors, by prime factorisation, by repeated subtraction.
- Euclid's division (remainder) algorithm and why it is correct.
- Comparing algorithms by number of steps.
- Using the GCD: LCM, simplifying fractions, tiling problems.
2. What Is an Algorithm?
- Input — what it starts with.
- Output — what it produces.
- Definiteness — every step is clear and unambiguous.
- Finiteness — it stops after a finite number of steps.
- Correctness — it gives the right output for every valid input.
The word comes from the name of the 9th-century scholar al-Khwārizmī, whose book explained the Indian decimal place-value system and methods of calculation.
3. The Addition Algorithm
Counting dots: to add 27 + 35 we could draw 27 dots and 35 dots and count all 62. This works but is slow — the steps grow with the size of the numbers.
Column addition uses place value:
- Write the numbers one below the other, lining up the units.
- Add the units digits. If the sum is 10 or more, write the units digit and carry 1 to the tens column.
- Repeat for each column, moving left, adding any carry.
- Write any final carry at the left.
Why carrying works: 10 units make 1 ten. In 27 + 35: 7 + 5 = 12 units = 1 ten + 2 units. Moving the extra ten to the tens column keeps the total the same.
Efficiency: column addition needs only about one step per digit. Adding two 10-digit numbers takes ~10 steps; counting dots would take billions.
4. Greatest Common Divisor (GCD)
The GCD (also called HCF) of two positive integers is the largest number that divides both.
Method 1 — List all divisors
Divisors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. Divisors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Common: 1, 2, 3, 4, 6, 12 → GCD = 12. Simple, but slow for big numbers.
Method 2 — Prime factorisation
36 = 2² × 3², 48 = 2⁴ × 3. Take the lowest power of each common prime: 2² × 3 = 12. Faster, but factorising very large numbers is itself hard.
Method 3 — Repeated subtraction
If d divides both a and b, then d divides a − b. So gcd(a, b) = gcd(a − b, b) for a > b.
gcd(48, 36) = gcd(12, 36) = gcd(12, 24) = gcd(12, 12) = 12.
5. Euclid's Algorithm (Division Version)
Repeatedly subtracting b from a is the same as dividing a by b and keeping the remainder. This gives a much faster method.
- Divide a by b: a = bq + r, with 0 ≤ r < b.
- If r = 0, then gcd = b. Stop.
- Otherwise replace (a, b) by (b, r) and repeat.
It works because gcd(a, b) = gcd(b, r): any common divisor of a and b also divides r = a − bq, and any common divisor of b and r divides a = bq + r.
Find gcd(1071, 462).
Solution:
| a | b | a = bq + r |
|---|---|---|
| 1071 | 462 | 1071 = 462 × 2 + 147 |
| 462 | 147 | 462 = 147 × 3 + 21 |
| 147 | 21 | 147 = 21 × 7 + 0 |
Remainder 0, so gcd = 21. Only 3 divisions!
6. Comparing the Methods
| Method | Steps for gcd(1071, 462) | Drawback |
|---|---|---|
| List divisors | Check ~460 numbers | Very slow for big numbers |
| Prime factorisation | Factorise both | Factorising large numbers is hard |
| Repeated subtraction | ~10 subtractions | Slow when one number is much bigger |
| Euclid (remainders) | 3 divisions | — (very efficient) |
Euclid's algorithm is efficient because the remainders shrink fast — at least halving every two steps.
7. Using the GCD
For any two positive integers: gcd(a, b) × lcm(a, b) = a × b.
- Simplifying fractions: 462/1071 → divide both by 21 → 22/51.
- Tiling: the largest square tile that exactly covers a 48 × 18 floor has side 6.
- Grouping: the most equal groups that 36 apples and 48 oranges can be shared into is 12.
- Two numbers are coprime if their gcd is 1.
8. Solved Problems (Board Pattern)
Use Euclid's algorithm to find gcd(867, 255).
Solution: 867 = 255 × 3 + 102; 255 = 102 × 2 + 51; 102 = 51 × 2 + 0. gcd = 51.
Find the LCM of 867 and 255.
Solution: lcm = 867 × 255 ÷ 51 = 17 × 255 = 4335.
An army band of 32 members marches behind a contingent of 616 members in the same number of columns. What is the largest possible number of columns?
Solution: gcd(616, 32): 616 = 32 × 19 + 8; 32 = 8 × 4 + 0. 8 columns.
9. Master Formula Table
| Rule | Statement |
|---|---|
| Division lemma | a = bq + r, 0 ≤ r < b |
| Subtraction step | gcd(a, b) = gcd(a − b, b) |
| Euclid step | gcd(a, b) = gcd(b, r) |
| Stop rule | gcd(b, 0) = b |
| GCD × LCM | gcd × lcm = a × b |
| From prime factors | gcd: lowest powers; lcm: highest powers |
10. Master Summary Table
| Topic | Key idea | Exam focus |
|---|---|---|
| Algorithm | Finite, definite, correct steps | Identify properties |
| Column addition | Carrying uses place value | Explain why it works |
| GCD methods | Divisors, primes, subtraction | Compare efficiency |
| Euclid's algorithm | gcd(a, b) = gcd(b, r) | Step-by-step computation |
| Applications | LCM, fractions, tiling, groups | Word problems |
11. Mind Map
- Input/output
- Finite, correct
- Dots → columns
- Carrying
- Divisors, primes
- Subtraction
- Remainders
- LCM, tiling
12. Tips and Tricks
- Set Euclid's algorithm out in a table: a, b, q, r — it prevents mistakes.
- The last non-zero remainder is the gcd.
- Check: the gcd must divide both original numbers.
- Stopping one step early and giving the quotient instead of the divisor.
- Dividing the smaller number by the larger one at the start.
- Confusing gcd (largest common divisor) with lcm (smallest common multiple).
13. Important One-liners
- An algorithm is a finite sequence of clear steps that solves a problem.
- The word "algorithm" comes from al-Khwārizmī.
- gcd(a, b) = gcd(b, a mod b).
- In Euclid's algorithm, the last non-zero remainder is the gcd.
- gcd × lcm = product of the two numbers.
- Coprime numbers have gcd 1.
14. Exam-pattern Questions with Detailed Answers
Find gcd(24, 60) by prime factorisation.
Show answer
24 = 2³ × 3, 60 = 2² × 3 × 5 → 2² × 3 = 12.
Answer: 12
Which property means an algorithm must stop?
- Definiteness
- Finiteness
- Input
- Output
Show answer
Finiteness.
Answer: (B)
Write 75 in the form 21q + r with 0 ≤ r < 21.
Show answer
75 = 21 × 3 + 12.
Answer: q = 3, r = 12
Use Euclid's algorithm to find gcd(135, 225).
Show answer
225 = 135 × 1 + 90; 135 = 90 × 1 + 45; 90 = 45 × 2 + 0. gcd = 45.
Answer: 45
gcd of two numbers is 9 and their product is 1620. Find their LCM.
Show answer
1620 ÷ 9 = 180.
Answer: 180
Use repeated subtraction to find gcd(91, 35).
Show answer
(91, 35) → (56, 35) → (21, 35) → (21, 14) → (7, 14) → (7, 7) → 7.
Answer: 7
Simplify 391/667 using Euclid's algorithm.
Show answer
667 = 391 × 1 + 276; 391 = 276 × 1 + 115; 276 = 115 × 2 + 46; 115 = 46 × 2 + 23; 46 = 23 × 2 + 0. gcd = 23. 391/667 = 17/29.
Answer: 17/29
A room is 825 cm × 675 cm. Find the side of the largest square tile that covers the floor exactly.
Show answer
825 = 675 × 1 + 150; 675 = 150 × 4 + 75; 150 = 75 × 2 + 0. Side = 75 cm.
Answer: 75 cm
Explain why any common divisor of a and b also divides the remainder r when a = bq + r.
Show answer
If d | a and d | b, write a = dm and b = dn. Then r = a − bq = dm − dnq = d(m − nq), so d | r.
Answer: r = d(m − nq), a multiple of d
Find the largest number that divides 245 and 1029 leaving remainder 5 in each case.
Show answer
The number divides 240 and 1024. gcd(1024, 240): 1024 = 240 × 4 + 64; 240 = 64 × 3 + 48; 64 = 48 × 1 + 16; 48 = 16 × 3 + 0. Answer 16.
Answer: 16
Show that consecutive integers n and n + 1 are always coprime.
Show answer
gcd(n + 1, n) = gcd(n, 1) by Euclid (n + 1 = n × 1 + 1), and gcd(n, 1) = 1.
Answer: gcd = 1 always
Write an algorithm (in numbered steps) that decides whether a number n > 1 is prime, and say how you could make it faster.
Show answer
1. Set d = 2. 2. If d × d > n, output "prime" and stop. 3. If d divides n, output "not prime" and stop. 4. Increase d by 1 and go to step 2. Faster: only test d = 2 and then odd d; we stop at √n because if n = ab with a ≤ b, then a ≤ √n.
Answer: Trial division up to √n
15. Quick Revision Summary
- An algorithm: input, output, definite, finite, correct.
- Column addition is efficient because of place value and carrying.
- GCD: listing → primes → subtraction → Euclid (fastest).
- Euclid: gcd(a, b) = gcd(b, r); last non-zero remainder is the gcd.
- gcd × lcm = a × b; use gcd for tiling, grouping and simplifying.