If we look through the divisors of 375 and 825 above, we see that the answer is 75. What if the numbers were 54000 and 81000?

Step-by-step solution

Idea: With long lists we cannot just “look”. Make a new list of common divisors: go through the first list and keep each number that is also in the second. Both lists are in increasing order, so the common list is too, and its last (rightmost) number is the greatest.

1. Compute both lists with the divisors algorithm. Each has 80 numbers, for example divisors(54000) = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, …, 18000, 27000, 54000] and divisors(81000) = [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, …, 27000, 40500, 81000]. Inspecting such lists by eye is unreliable, so we work systematically.1 mark
2. Start with an empty list of common divisors. For each divisor of 54000, check whether it is in the list for 81000; if it is, add it. (1 is always added, since 1 divides every number.) For example 16 is not added (16 does not divide 81000), and 18000 is not added (81000 ÷ 18000 = 4.5).1 mark
3. The common list has 64 numbers: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, …, 6750, 9000, 13500, 27000]. Since both lists are in increasing order, the common list is also in increasing order.½ mark
4. So the greatest common divisor is the rightmost element: gcd(54000, 81000) = 27000.½ mark

Check: 54000 = 2 × 27000 and 81000 = 3 × 27000. Since 2 and 3 have no common factor except 1, no larger number divides both ✓.

Answer to write in the exam

Common mistakes that cost marks

• Taking the rightmost element of one of the original lists (54000) instead of the rightmost element of the common list.
• Stopping when the first big common number is found by eye (for example 13500) without checking the whole list.
• Forgetting that the common list is in increasing order only because the original lists were made in increasing order.

How this can come in the exam

Try one yourself

Find gcd(4800, 7200).

More questions like this

• Suppose we want to compute gcd(375, 825).
• Suppose List 1 and List 2 are two lists of numbers in increasing order.
• Describe an algorithm to compute the least common multiple (lcm) of two numbers.
• Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).
• Let us keep track of a quantity called most-recent-common-divisor. We know that 1 is always a common divisor, so we can start with most-recent-common-divisor set to 1. We then scan all numbers from 2 to min(m, n). For each k from 2 to min(m, n), if k divides both m and n, update most-recent-common-divisor to k. Example: Let m = 6, n = 12.

All Algorithms questions · All maths questions