Why does Euclid’s GCD algorithm work?

We start with the definition of the GCD of two numbers. (Throughout this article, ‘number’ means ‘integer.’) Definition: The GCD or ‘Greatest Common Divisor’ of two numbers, also called the Highest Common Factor (HCF), is: • A divisor of both the numbers, i.e., it is a common divisor. • Of all the common divisors, it is the greatest. Note that the GCD is a multiple of every other common factor of the two numbers