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.

Step-by-step solution

Idea: We do not need a list of all common divisors: each new common divisor is larger than the earlier ones, so we only remember the latest. When the scan ends, the latest common divisor is the greatest.

1. min(6, 12) = 6, so we scan k = 2, 3, 4, 5, 6. Initially most-recent-common-divisor = 1.½ mark
2. k = 2 divides both 6 and 12 → update to 2.
   k = 3 divides both 6 and 12 → update to 3.½ mark
3. k = 4 does not divide 6 → remains 3.
   k = 5 does not divide 6 → remains 3.½ mark
4. k = 6 divides both 6 and 12 → update to 6. Scan complete. gcd(6, 12) = 6.½ mark

Check: 6 divides 12, so the greatest common divisor of 6 and 12 must be 6 itself ✓.

Answer to write in the exam

Common mistakes that cost marks

• Scanning up to max(6, 12) = 12. A common divisor cannot be larger than the smaller number, so the scan stops at 6.
• Updating when k divides only one of the numbers (for example k = 4 divides 12 but not 6).
• Starting with most-recent-common-divisor = 0 instead of 1; if no larger common divisor is found, the answer must still be 1.

How this can come in the exam

Try one yourself

Use most-recent-common-divisor to find gcd(9, 15).

More questions like this

• 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?
• What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?
• Let us assume that m ≥ n. Then, gcd(m, n) is the same as gcd(n, m − n). Why is this the case?
• Euclid’s algorithm for gcd(m, n): 1. If m < n, reverse the numbers and compute gcd(n, m) 2. If n = 0, report the answer as m 3. Otherwise, reduce the problem to compute gcd(n, m − n). Let us apply this algorithm to gcd(375, 825), the problem that we saw before.
• Are we close to our original goal of finding an algorithm where the effort is proportional to the number of digits?

All Algorithms questions · All maths questions