• Foundation
  • About 15 min
  • 5 practice questions

Euclid's subtraction algorithm for the gcd

Explain why gcd(m, n) = gcd(n, m − n), run Euclid's subtraction algorithm with its stopping rule, and see why it can still be slow when one number is much smaller than the other.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Prove that m and n have the same common divisors as n and m − n.
  • Execute Euclid's subtraction algorithm, including the swap and the stopping rule gcd(m, 0) = m.
  • Explain why the subtraction method can need a number of steps that grows with the value of the numbers.

The gcd algorithms of the last lesson try every possible divisor. A much cleverer idea was written down by Euclid in his book Elements, more than two thousand years ago (historians think other Greek mathematicians knew it earlier). It replaces the problem with a smaller one of the same kind, again and again, until the answer is obvious.

The key fact

If m ≥ n, then gcd(m, n) = gcd(n, m − n). Also, gcd(m, 0) = m.

Why it is true. Suppose d divides both m and n. Then m = ad and n = bd for whole numbers a and b, so m − n = ad − bd = (a − b)d. Hence d divides m − n as well.

Conversely, suppose d divides both n and m − n, say n = xd and m − n = yd. Then m = n + (m − n) = xd + yd = (x + y)d, so d divides m.

So the pair (m, n) and the pair (n, m − n) have exactly the same common divisors, and therefore the same greatest one. In pictures: if blocks of length d can exactly tile lengths m and n, then laying n alongside m shows that blocks of length d also exactly tile the leftover piece m − n.

When to stop. gcd(23, 23) is clearly 23, and one more reduction turns it into gcd(23, 23 − 23) = gcd(23, 0). Every number divides 0, so the common divisors of 23 and 0 are just the divisors of 23, and the greatest is 23. In general, gcd(m, 0) = m.

The algorithm

  1. If m < n, swap the numbers and compute gcd(n, m) instead.
  2. If n = 0, report m as the answer.
  3. Otherwise, replace the problem by gcd(n, m − n) and go back to step 1.

Euclid's subtraction algorithm repeats until n = 0

  1. Is m < n? If so, swap the two numbers
  2. Is n = 0? If so, stop: the answer is m
  3. Reduce Replace (m, n) by (n, m − n)

Then back to step 1: Is m < n?

Worked example 1: gcd(84, 36)

Each row is one pass through the steps
Current problemWhat happensNext problem
gcd(84, 36)Reduce: 84 − 36 = 48gcd(36, 48)
gcd(36, 48)36 < 48, swapgcd(48, 36)
gcd(48, 36)Reduce: 48 − 36 = 12gcd(36, 12)
gcd(36, 12)Reduce: 36 − 12 = 24gcd(12, 24)
gcd(12, 24)12 < 24, swapgcd(24, 12)
gcd(24, 12)Reduce: 24 − 12 = 12gcd(12, 12)
gcd(12, 12)Reduce: 12 − 12 = 0gcd(12, 0)
gcd(12, 0)n = 0, stopAnswer 12

Five reductions gave gcd(84, 36) = 12. Check: 84 = 12 × 7 and 36 = 12 × 3, and 7 and 3 share no factor except 1.

Worked example 2: gcd(35, 15)

gcd(35, 15) → reduce: 35 − 15 = 20 → gcd(15, 20) → swap → gcd(20, 15) → reduce: 20 − 15 = 5 → gcd(15, 5) → reduce: 15 − 5 = 10 → gcd(5, 10) → swap → gcd(10, 5) → reduce → gcd(5, 5) → reduce → gcd(5, 0) → answer 5.
Check: 35 = 5 × 7 and 15 = 5 × 3.

How fast is it?

For gcd(375, 825), Euclid's method needs 7 reductions, far fewer than checking 375 possible divisors. But it is not always fast. Try gcd(51, 2): the reductions give gcd(2, 49), then (after a swap) gcd(2, 47), gcd(2, 45), and so on, taking away 2 each time, down to gcd(2, 1), then gcd(1, 1) and gcd(1, 0). That is 27 reductions to find the answer 1. In general, gcd(2k + 1, 2) needs about k reductions. So the number of steps can grow with the value of the numbers, not just their number of digits. The last lesson fixes this.

Key takeaways

  • If d divides m and n, it divides m − n; if d divides n and m − n, it divides m. So gcd(m, n) = gcd(n, m − n).
  • Euclid's algorithm: swap if m < n, stop with answer m when n = 0, otherwise reduce to gcd(n, m − n).
  • The method reduces a problem to a smaller problem of the same kind.
  • Repeated subtraction can be slow: gcd(2k + 1, 2) needs about k reductions.

Check your understanding

  1. 1. By Euclid's key fact, gcd(91, 35) equals which of these?

    1. gcd(35, 56)
    2. gcd(91, 56)
    3. gcd(35, 126)
    4. gcd(56, 126)
    Show answer

    Answer: A. With m = 91 ≥ n = 35, gcd(m, n) = gcd(n, m − n) = gcd(35, 91 − 35) = gcd(35, 56). The answer to both is 7.

  2. 2. Euclid's algorithm reaches gcd(17, 0). What is the answer?

    1. 0
    2. 1
    3. 17
    4. It cannot be found
    Show answer

    Answer: C. Every number divides 0, so the common divisors of 17 and 0 are the divisors of 17, and the greatest is 17. The stopping rule says gcd(m, 0) = m.

  3. 3. d divides both m and n. Which argument shows that d divides m − n?

    1. m − n is always smaller than m
    2. m − n is always even
    3. d is always 1
    4. m = ad and n = bd, so m − n = (a − b)d
    Show answer

    Answer: D. Writing m = ad and n = bd gives m − n = ad − bd = (a − b)d, which is d times a whole number, so d divides m − n. Being smaller than m proves nothing about divisibility.

  4. 4. Use Euclid's subtraction algorithm to find gcd(45, 18).

    1. 3
    2. 18
    3. 6
    4. 9
    Show answer

    Answer: D. gcd(45, 18) → 45 − 18 = 27 → gcd(18, 27) → swap → gcd(27, 18) → 27 − 18 = 9 → gcd(18, 9) → 18 − 9 = 9 → gcd(9, 9) → gcd(9, 0) → 9. Check: 45 = 9 × 5 and 18 = 9 × 2.

  5. 5. About how many reductions does Euclid's subtraction algorithm need for gcd(101, 2)?

    1. About 3
    2. About 50
    3. About 10
    4. Exactly 2
    Show answer

    Answer: B. Each reduction takes away only 2: 101 → 99 → 97 → ... → 1. That is 50 subtractions to reach 1, plus a couple more to finish, about 50 in all. For gcd(2k + 1, 2) it needs about k reductions, and here k = 50.

Privacy · Terms · Refunds · Delivery