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.
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.
The gcd is the last nonzero remainder, never the first. In 147, 21, 0 the answer is 21. Reading only the first line gives 147, which is wrong.
Repeat division to the gcd, run it backwards for the combination, and let the lemma secure unique factorisation.
The rewritten readings were written for this dataset.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
Optional connections
This opens up
14 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.