Euclid's Algorithm and Bezout's Identity
Find a greatest common divisor by repeated division instead of by factorising, then run the algorithm backwards to write it as a combination of the two numbers.
What a learner can do afterwards
- Run the algorithm on a large pair and explain why it terminates
- Back-substitute to express the gcd as an integer combination of the inputs
- Deduce Euclid's lemma and, from it, uniqueness of prime factorisation
1 · Read
The Euclidean algorithm finds the largest number dividing both inputs through repeated remainders. Write the larger number with quotient and remainder, replace the pair by the smaller number and the remainder, and repeat until a zero remainder appears. For 270 and 192 the remainders run 78, 36, 6, 0, so the last nonzero remainder, 6, is the gcd.
Try it on 1071 and 462: 1071 = 462 times 2 plus 147, then 462 = 147 times 3 plus 21, then 147 = 21 times 7 plus 0, so the gcd is 21. It always stops because the remainders keep shrinking, and shrinking whole numbers must reach 0. One division per step beats listing hundreds of divisors.
Back substitution turns the chain into a combination of the original pair, which is Bezout's identity. Each remainder can be rewritten from the line above it, so working backwards expresses the gcd with the two inputs. For 270 and 192 this gives 6 = 5 times 270 plus negative 7 times 192, and you can check that 1350 minus 1344 is indeed 6.
The same idea proves Euclid's lemma: a prime dividing a product must divide one of the factors. From the lemma follows the uniqueness of prime factorisation, so every whole number over 1 breaks into primes in exactly one way, such as 24 = 2 times 2 times 2 times 3.
Repeat division to the gcd, run it backwards for the combination, and let the lemma secure unique factorisation.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.