Algorithms and the addition algorithm
A recipe lists steps in order so that anyone can cook the same dish. A maths algorithm is a recipe that always gives the right answer.
An algorithm is a finite list of clear, ordered steps that solves a problem and ends. Column addition is one: add digits from the right, write the unit digit and carry the rest.
Formula: Algorithm = clear steps + order + ends
In the figure: 478 + 365: 8 + 5 = 13 (write 3, carry 1); 7 + 6 + 1 = 14 (write 4, carry 1); 4 + 3 + 1 = 8. Answer 843.
Rule 1: Follow the algorithm — Do each step exactly as written and do not skip a carry.
- Easy: 59 + 27 = 86.
- Medium: 999 + 1 = 1000 (carry runs through).
- Exam-type: 1234 + 4321 = 5555 (no carry).
Rule 2: What makes a good algorithm — Clear steps, same answer every time, and it must stop.
- Easy: "Keep adding 1 forever" is not an algorithm; it never ends.
- Medium: "Make it about right" is not clear enough.
- Exam-type: Steps must be in order: carry before the next column.
The same problem can have several correct algorithms.
Forgetting the carry or adding it to the wrong column.
"Right to left, carry along."
Practice questions
- 1Which is a necessary feature of every algorithm?
- 2While adding 70 + 21 column by column from the ones place, what carry goes into the tens column?
- 3How many times does a carry occur while adding 638 + 833 column by column?
- 4Adding 259 + 608: in the tens column, what digit is written and what carry goes to the hundreds column?
- 5At most how many digits can the sum of a 5-digit number and a 1-digit number have?
- 6Maya added 754 + 638 and got 1192. In which column of her answer is the first wrong digit (counting from the right)?
- 7How many carries occur while adding 4885 + 7024 column by column (ones, tens, hundreds, thousands)?
- 8Adding 54 + 93 + 16, what carry goes from the ones column into the tens column?
Show answers (try them yourself first)
- 1Each step is clear and exact
- 20
- 32
- 4digit 6, carry 0
- 56
- 6hundreds column
- 72
- 81
Finding divisors
To seat 36 students in equal rows you need the numbers that divide 36: rows of 1, 2, 3, 4, 6, 9, 12, 18 or 36.
A divisor of n divides it exactly. Divisors come in pairs whose product is n. Test d = 1, 2, 3, … only up to √n: each divisor d ≤ √n gives its partner n ÷ d.
Formula: d | n ⇒ (n ÷ d) | n; check d ≤ √n
In the figure: For 36 test up to 6; each hit gives a pair: 1 and 36, 2 and 18, 3 and 12, 4 and 9, 6 and 6.
Rule 1: List all divisors — Test 1, 2, 3, … up to √n and write both partners.
- Easy: 12: 1, 2, 3, 4, 6, 12.
- Medium: 30: 1, 2, 3, 5, 6, 10, 15, 30.
- Exam-type: 17 (prime): 1 and 17 only.
Rule 2: Count divisors — A perfect square has an odd number of divisors because the square root pairs with itself.
- Easy: 36 has 9 divisors (odd, a perfect square).
- Medium: To test 97 for primes check only up to 9: none divides, so prime.
- Exam-type: Every number has divisors 1 and itself.
Stopping at √n saves a lot of testing.
Forgetting the partner divisors, e.g. listing 1, 2, 3, 4, 6 for 12 and missing 12.
"Find one, get one free."
Practice questions
- 1Which number is a divisor of every natural number?
- 2Which list shows all the divisors of 18?
- 3How many divisors does 36 have?
- 46 is a divisor of 180. Which other number is also a divisor of 180 (the partner of 6)?
- 54 is a divisor of 48. Which other number is also a divisor of 48 (the partner of 4)?
- 6What is the smallest divisor of 253 that is greater than 1?
- 7What is the smallest divisor of 161 that is greater than 1?
- 8What is the sum of all the divisors of 60?
Show answers (try them yourself first)
- 11
- 21, 2, 3, 6, 9, 18
- 39
- 430
- 512
- 611
- 77
- 8168
Common divisors and GCD
To cut two ribbons of 12 m and 18 m into equal pieces with no waste, the piece length must divide both. The longest such piece is the GCD.
A common divisor divides both numbers. The GCD (greatest common divisor, मसावि) is the largest of them. Numbers with GCD 1 are co-prime.
Formula: GCD(12, 18) = 6; GCD(a, b) = 1 ⇒ co-prime
In the figure: Divisors of 12 and of 18 overlap in 1, 2, 3, 6; the biggest is 6.
Rule 1: Find the GCD — List divisors of both and pick the largest common one, or use prime factors.
- Easy: GCD(8, 12) = 4.
- Medium: GCD(15, 28) = 1, so co-prime.
- Exam-type: GCD(36, 48) = 12.
Rule 2: Use the GCD — Largest equal groups or tiles with no leftover use the GCD.
- Easy: Share 24 pens and 36 pencils equally in the most kits: 12 kits.
- Medium: Square tiles for 120 cm × 80 cm floor: side 40 cm.
- Exam-type: Simplify 18/24: divide by 6 to get 3/4.
The GCD never exceeds the smaller number.
Confusing GCD (largest divisor) with LCM (smallest multiple).
"Greatest that goes into both."
Practice questions
- 1How many common divisors do 24 and 36 have?
- 2What is the greatest common divisor (GCD) of 16 and 24?
- 3Find the greatest common divisor of 78 and 117.
- 4Are 72 and 16 coprime (is their only common divisor 1)?
- 5Using the GCD, write 15/21 in its simplest form.
- 6A club has 56 boys and 98 girls. They are put into teams so that each team has the same number of boys and the same number of girls, with nobody left out. What is the largest possible number of teams?
- 7Find the greatest number that divides 60, 90 and 150 exactly.
- 8Two numbers have GCD 8. They are 8 × 5 and 8 × 6 where 5 and 6 are coprime. What is their sum?
Show answers (try them yourself first)
- 16
- 28
- 339
- 4No
- 55/7
- 614
- 730
- 888
Euclid's algorithm
Finding the largest square tile for a floor by trial is slow. Euclid's idea: keep cutting the leftover strip off until nothing is left.
Euclid's algorithm: divide the larger number by the smaller, then replace (a, b) by (b, remainder). Repeat until the remainder is 0; the last non-zero remainder is the GCD.
Formula: GCD(a, b) = GCD(b, a mod b)
In the figure: 48 ÷ 18 leaves 12, 18 ÷ 12 leaves 6, 12 ÷ 6 leaves 0, so GCD(48, 18) = 6.
Rule 1: Run the algorithm — Each line: bigger = quotient × smaller + remainder.
- Easy: GCD(100, 75): 100 = 1×75 + 25, 75 = 3×25 + 0, so 25.
- Medium: GCD(252, 105) = 21.
- Exam-type: GCD(17, 5): 17 = 3×5 + 2, 5 = 2×2 + 1, 2 = 2×1 + 0, so 1.
Rule 2: Why it works — Any number dividing a and b also divides the remainder, so the pair keeps the same GCD but gets smaller.
- Easy: GCD(a, b) = GCD(a − b, b).
- Medium: Remainders keep getting smaller, so it must stop.
- Exam-type: It works for huge numbers where listing divisors is impossible.
Euclid's method is far faster than listing all divisors.
Stopping at the last remainder 0 instead of the one before it.
"Divide, take the leftover, repeat."
Practice questions
- 1What is the remainder when 147 is divided by 13?
- 2By Euclid's algorithm, GCD(263, 62) = GCD(?, ?). Which pair comes next?
- 3Use Euclid's algorithm to find GCD(252, 99).
- 4How many division steps does Euclid's algorithm need to find GCD(432, 101) (until the remainder is 0)?
- 5In Euclid's algorithm for 403 and 125, the first division gives remainder 28. What is the second remainder (when 125 is divided by 28)?
- 6Find GCD(361, 228) using Euclid's algorithm.
- 7Consecutive Fibonacci numbers are the hardest case for Euclid's algorithm. How many division steps does it take to find GCD(233, 144)?
- 8150 is divided by 48 and the remainder is 6. Given that GCD(48, 6) = 6, what is GCD(150, 48)?
Show answers (try them yourself first)
- 14
- 2(62, 15)
- 39
- 47
- 513
- 619
- 711
- 86
Euclid's algorithm
In the app you can move this figure with your finger.
Open in the appCounting steps and efficiency
Two roads reach the same town; the shorter has fewer turns. A good algorithm uses fewer steps for the same answer.
The efficiency of an algorithm is judged by how many steps it needs. Compare algorithms by counting steps for the same input. Steps usually grow with the input size.
Formula: Fewer steps for the same answer = more efficient
In the figure: Euclid finds GCD(1071, 462) = 21 in 3 divisions; listing divisors of both takes far more work.
Rule 1: Count the steps — Count each division (or each test) as one step.
- Easy: Checking 97 for primes up to 9: 9 tests, not 96.
- Medium: GCD(48, 18) by Euclid: 3 divisions.
- Exam-type: Adding 100 numbers one by one: 99 additions.
Rule 2: Compare algorithms — Pick the algorithm that needs fewer steps for large inputs.
- Easy: Pairing 1 + 100, 2 + 99 … needs 50 pairs; adding one by one needs 99.
- Medium: Testing divisors up to √n beats testing up to n.
- Exam-type: Doubling the input size usually increases the steps.
Efficient algorithms matter most for very large numbers.
Judging an algorithm by how short it is to write, not by the steps it takes.
"Fewer steps, faster answer."
Practice questions
- 1A list has 26 different numbers. The greatest one is found by comparing every number with the best so far. How many comparisons are needed?
- 2How many additions are needed to find the total of 15 numbers by adding them one at a time?
- 3To find common items in two lists of 25 and 8 entries, every entry of the first list is compared with every entry of the second list. How many comparisons are made?
- 4Two lists have 50 and 20 entries. You read every entry of the first list once and then every entry of the second list once. How many entries do you read in all?
- 5Method A compares every item of a 15-entry list with every item of an 18-entry list. Method B just scans both lists once. How many more steps does Method A take than Method B?
- 6A step takes 5 milliseconds. How many milliseconds does a method with m × n = 200 × 50 steps need?
- 7Two lists each have 1000 entries. Method A takes 1000×1000 steps and Method B takes 1000+1000 steps. How many times as many steps does A take as B?
- 8Two clerks read two lists at the same time, one clerk per list. The lists have 60 and 55 entries. How many rounds (one entry per clerk per round) are needed until both lists are completely read?
Show answers (try them yourself first)
- 125
- 214
- 3200
- 470
- 5237
- 650000
- 7500
- 860