Euclidean algorithm
The following proof is inspired by Euclid's version of Euclidean algorithm, which proceeds by using only subtractions.