How does the Euclidean algorithm find a greatest common divisor?

The Euclidean algorithm is a computationally efficient procedure for finding the greatest common divisor (GCD) of two numbers, as described by the Greek mathematician Euclid in his Elements.1

The method relies on a process of successive division and calculation of remainders:

• Divide the first number by the second and note the remainder.
• Replace the first number with the previous divisor and the second number with the previous remainder.
• Repeat this division process until the remainder is 0.
• The last nonzero remainder obtained before reaching 0 is the greatest common divisor.1

For example, to find the GCD of 56 and 12:
1. $56=4\times 12+8$
2. $12=1\times 8+4$
3. $8=2\times 4+0$

Since the final remainder is 0, the last nonzero remainder, 4, is the greatest common divisor.1