Euclid's algorithm
Tonight's idea
\(\gcd(a, b)\), the greatest common divisor, is the largest whole number dividing both \(a\) and \(b\). Grade 6 called it the GCF and found it from prime factors, which is slow for big numbers. Euclid, around 300 BC, gave a method that never factors anything.
Divide \(a\) by \(b\): \(a = qb + r\), with quotient \(q\) and remainder \(r\). The key fact is
\(\gcd(a, b) = \gcd(b, r)\). The pair \((a, b)\) and the pair \((b, r)\) have exactly the same common divisors.
Why? Anything dividing \(a\) and \(b\) divides \(a - qb = r\). Anything dividing \(b\) and \(r\) divides \(qb + r = a\). Same common divisors, so the same greatest one.
Now repeat. Each remainder is smaller than the last, so the numbers shrink and must reach 0. Since \(\gcd(x, 0) = x\), the last nonzero remainder is the answer.
The picture is the same algorithm: cut the biggest squares you can from a \(1071 \times 462\) rectangle, then repeat on the leftover strip. The square that finishes the last strip also tiles every earlier strip, and so the whole rectangle. Its side is the gcd.
Watch one: \(\gcd(1071, 462)\)
\[1071 = 2 \times 462 + 147, \qquad 462 = 3 \times 147 + 21, \qquad 147 = 7 \times 21 + 0.\]
So \(\gcd(1071, 462) = 21\). Three divisions. Check: \(1071 = 21 \times 51\) and \(462 = 21 \times 22\), and 51 and 22 share nothing. Compare the picture: two 462-squares, three 147-squares, seven 21-squares. The quotients 2, 3, 7 count the squares.
Two bonuses. The fraction \(\tfrac{462}{1071}\) simplifies in one step to \(\tfrac{22}{51}\). And since \(\gcd \times \text{lcm} = a \times b\), the least common multiple is \(1071 \times 462 \div 21 = 23\,562\).
Enter your own pair and watch the squares get cut at mathdetours.com/demos/euclid.html.
Your turn
- Use Euclid's algorithm to find (a) \(\gcd(252, 105)\) and (b) \(\gcd(1001, 273)\). Write every step in the form \(a = qb + r\).
- Simplify \(\tfrac{748}{2024}\) fully, using one gcd computation and two divisions.
- (a) Find \(\gcd(323, 221)\). (b) Hence write both 323 and 221 as products of primes. Neither looks easy to factor until the algorithm hands you a factor.
- (a) Draw the rectangle picture for \(\gcd(84, 36)\): a \(84 \times 36\) rectangle. Which squares appear, how many of each, and what is the gcd? (b) Use the key fact to explain why two consecutive whole numbers, such as 1000 and 1001, always have gcd 1.
Stretch: the slowest pair
Run the algorithm on 89 and 55. Count the divisions, and notice every quotient but the last is 1. What is special about 89, 55, 34, 21, …? Then show that after two divisions the first number has at least halved, so two numbers near a million need at most about 40 divisions.
Answers
- (a) \(252 = 2 \times 105 + 42\), \(105 = 2 \times 42 + 21\), \(42 = 2 \times 21 + 0\). gcd 21. (b) \(1001 = 3 \times 273 + 182\), \(273 = 1 \times 182 + 91\), \(182 = 2 \times 91 + 0\). gcd 91.
- \(2024 = 2 \times 748 + 528\), \(748 = 1 \times 528 + 220\), \(528 = 2 \times 220 + 88\), \(220 = 2 \times 88 + 44\), \(88 = 2 \times 44\). gcd 44, and \(\tfrac{748}{2024} = \tfrac{17}{46}\).
- (a) \(323 = 1 \times 221 + 102\), \(221 = 2 \times 102 + 17\), \(102 = 6 \times 17\). gcd 17. (b) \(323 = 17 \times 19\) and \(221 = 13 \times 17\).
- (a) Two squares of side 36 leave a \(12 \times 36\) strip; three squares of side 12 finish it. gcd 12. (b) \(1001 = 1 \times 1000 + 1\), so \(\gcd(1001, 1000) = \gcd(1000, 1) = 1\). In general \(\gcd(n + 1, n) = \gcd(n, 1) = 1\).
Stretch. \(89 = 1 \times 55 + 34\), \(55 = 1 \times 34 + 21\), \(34 = 1 \times 21 + 13\), \(21 = 1 \times 13 + 8\), \(13 = 1 \times 8 + 5\), \(8 = 1 \times 5 + 3\), \(5 = 1 \times 3 + 2\), \(3 = 1 \times 2 + 1\), \(2 = 2 \times 1 + 0\). Nine divisions for a gcd of 1. The numbers are consecutive Fibonacci numbers: each is the sum of the next two, so each division goes in exactly once with the next Fibonacci number left over. These pairs are the slowest the algorithm ever gets. Halving: after one division, \((a, b)\) becomes \((b, r)\). If \(b \le a/2\) then \(r \lt b \le a/2\). If \(b > a/2\) then \(q = 1\) and \(r = a - b \lt a/2\). Either way \(r \lt a/2\), and \(r\) is the first number two steps on. A million is about \(2^{20}\), so it halves to 1 in about 20 pairs of steps: 40 divisions at most.