Suppose we want to compute gcd(375, 825).

Step-by-step solution

Idea: Work straight from the meaning of gcd: list all divisors of each number, keep the ones that appear in both lists, and pick the largest. Because the lists are in increasing order, the largest common divisor is the last one in the common list.

1. Step 1: divisors-of-m = divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375].½ mark
2. Step 2: divisors-of-n = divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825].½ mark
3. Steps 3 and 4: start with common-divisors = [ ]. Check each divisor of 375 in the list for 825:
   1 ✓, 3 ✓, 5 ✓, 15 ✓, 25 ✓, 75 ✓, 125 ✗ (825 ÷ 125 = 6.6), 375 ✗ (825 ÷ 375 = 2.2).1 mark
4. So common-divisors = [1, 3, 5, 15, 25, 75].½ mark
5. Step 5: the rightmost element is 75. So gcd(375, 825) = 75.½ mark

Check: 375 = 5 × 75 and 825 = 11 × 75; 5 and 11 share no factor, so 75 is the greatest ✓.

Answer to write in the exam

Common mistakes that cost marks

• Missing 11, 33, 55 or 165 in the list for 825, or 125 in the list for 375. These do not change the answer here, but a missed common divisor could.
• Reporting the rightmost element of divisors-of-m (375) instead of the rightmost common divisor.
• Adding numbers to the common list that are in only one list (for example 11).

How this can come in the exam

Try one yourself

Use the lists-of-divisors algorithm to find gcd(45, 75).

More questions like this

• 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.
• How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?

All Algorithms questions · All maths questions