Theorem. Euclidean Algorithm [000Y]

The euclidean algorithm starts with two integers and and performs successive division with remainder until it is zero, like follows.

The algorithm computes the the greatest common divisor of and . For a proof see the Euclid's Theorem.