Why the Euclidean algorithm works

Inclusion 1. If $d\mid a$ and $d\mid b$, then $d\mid a-bq=r$. So $d$ is a common divisor of $b$ and $r$.

Inclusion 2. If $d\mid b$ and $d\mid r$, then $d\mid bq+r=a$. So $d$ is a common divisor of $a$ and $b$.

Conclusion. The two pairs have the same common divisors, hence the same greatest one. The Euclidean algorithm terminates because the remainders strictly decrease: $r<b$, and each new remainder is strictly smaller than the previous one. It stops when the remainder is $0$, and the last nonzero remainder is the divisibility.