Proof of the Euclidean algorithm

Common divisors. If $d\mid a$ and $d\mid b$, then $d\mid a-bq=r$. Conversely, if $d\mid b$ and $d\mid r$, then $d\mid bq+r=a$.

Conclusion. Both pairs have the same common divisors, hence the same greatest one. The Euclidean algorithm terminates because remainders strictly decrease, and stops at the last nonzero remainder, which is the gcd.