Algorithms · 3 marks

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?

Answer: The first k that divides both numbers is the gcd, so we can stop there; no list and no most-recent-common-divisor are needed. But the update rule must change: if we kept updating all the way down, the last update would be k = 1 and the answer would wrongly be 1.

Step-by-step solution

Idea: Scanning downwards meets the common divisors from largest to smallest, so the first one met is the greatest. Stopping there usually saves many checks.

The last algorithm scans k = 2, 3, …, min(m, n) and keeps the most recent common divisor; going upwards, the most recent one is the largest.
Going backwards, k = min(m, n), min − 1, …, 1 meets the common divisors from largest to smallest. So the first k that divides both m and n is the gcd.1 mark
If we kept the old rule (“update most-recent-common-divisor whenever k divides both”) and scanned all the way down, the last update would be at k = 1, since 1 divides every number. The algorithm would report 1, which is wrong. So the rule must change to: stop at the first common divisor and report it.1 mark
New algorithm: for each k from min(m, n) down to 1: if k divides both m and n, report k as gcd(m, n) and stop. (It always stops, at k = 1 at the latest.)½ mark
Effect on the work: gcd(6, 12) is found at once (k = 6, one check). gcd(375, 825) is found at k = 75 after 301 checks, instead of 374 checks going up. In the worst case, when the gcd is 1, we still check every number, so the work is still proportional to the size of the smaller number.½ mark

The first common divisor met when scanning down from min(m, n) is the gcd, so the algorithm can stop there (keeping updates to the end would wrongly give 1). It is often faster, but when the gcd is small it still checks almost every number.

Answer to write in the exam

Scanning down from min(m, n), common divisors are met from largest to smallest.

First k dividing both m and n = gcd(m, n).

Old update rule kept → last update at k = 1 → answer 1 ✗

New rule: for k = min(m, n) down to 1, if k divides both m and n, report k and stop.

e.g. gcd(6, 12): k = 6 divides both → 6 (1 check)

∴ We stop at the first common divisor found; fewer checks unless the gcd is small.

Common mistakes that cost marks

Keeping the update rule unchanged and scanning to 1, which always ends with the answer 1.
Starting the backward scan at max(m, n) instead of min(m, n).
Claiming the backward scan is always faster. When the gcd is 1 it still checks every number.

How this can come in the exam

MCQ (1 mark)

Scanning backwards from min(m, n) and stopping at the first common divisor, how many values of k are checked to find gcd(40, 64)?

Show answer

(C) 33
k = 40, 39, …, 8: the first common divisor is 8. That is 40 − 8 + 1 = 33 checks.

Try one yourself

Use the backward scan to find gcd(27, 45). How many values of k are checked?