Euclidean algorithm

Finding the GCD of

a
a >b
b
multiplier of the division of a by b
remainder of the last division

The GCD is the last remainder different of 0.

The GCD of is