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.