Invariance and termination of the Euclidean algorithm

Step 1 (Same common divisors). Let $d$ be any integer dividing both $a$ and $b$, so $a=dx$ and $b=dy$ for integers $x,y$. Then $r=a-bq=dx-dyq=d(x-yq)$, so $d\mid r$, meaning $d$ divides both $b$ and $r$. Conversely, if $d$ divides both $b$ and $r$, say $b=dy$ and $r=dz$, then $a=bq+r=dyq+dz=d(yq+z)$, so $d\mid a$, meaning $d$ divides both $a$ and $b$.

Step 2 (Equality of greatest common divisors). Because the pairs $(a,b)$ and $(b,r)$ have the exact same set of common divisors, they have the exact same maximum element: $\gcd(a,b)=\gcd(b,r)$.

Step 3 (Finite termination). Each division step produces a remainder satisfying $0\le r<b$, so the sequence of second entries $b > r_1 > r_2 > \cdots \ge 0$ is a strictly decreasing sequence of non-negative integers. Such a sequence can have at most $b$ steps before reaching $0$; at the step $\gcd(r_{k-1},r_k)=\gcd(r_k,0)=r_k$, the last nonzero remainder $r_k$ is $\gcd(a,b)$.