 Euclidean algorithm

The Euclidean algorithm repeatedly replaces $(a,b)$ by $(b,a\mathrm{mod}b)$ and terminates at $\gcd (a,b)$.